Now that you've cleared out the gold mine, head back to Fourside.
Receive the Diamond
On your way to Fourside, the miner's brother will drive up with his backhoe and tell you that they haven't found gold yet, but they did find a huge diamond. He hands it over to you.
Give Miss Fake the Diamond
Take the diamond and go get a ticket at Topolla Theater. Go show the diamond to Miss Fake. She'll recognize how valuable the diamond is, and will rip up the Runaway Five's contract right then and there. After that, the Runaway Five will do their final performance, at the end of which they drive off in their bus.
Visit the Newly Opened Department Store
At this point, the Department Store has finally opened. You should go there, but be warned: you're about to get separated from Paula for a while. And you'll have to fight your way out.
While in the Department Store, or before going there, move any valuable items out of Paula's inventory and move it into either Ness's inventory, Jeff's inventory, or Escargo Express. Consider investing in a Teddy Bear or two. And fill Jeff's inventory with Big Bottle Rockets, which you can buy from the military dude in a storage room of the department store.
If you're ready, go into the Department Store and buy any supplies that you think you'll need (including the Big Bottle Rockets.) When you try to leave the Department Store, the lights will go out and an alien will zoom past, taking Paula away with it. Then over the loudspeaker, the alien will urge you to go to the office at the top of the department store to get Paula back. You can't leave, so you'll have to do what the loudspeaker says.
Go to the Office on the Top Floor
The enemies here are really tough. You'll only need one or two bottle rockets for the boss battle at the end of the department store, so use the rest on the enemies here, to give yourself a fighting chance.
In the office on the top floor, you will find the alien who kidnapped Paula. However, Paula herself is not here. You'll have to fight the alien to find out where she is. Find out how to defeat the Department Store Spook.
Once you defeat it, the alien will say something about Paula and Monotoli. Sounds like she's being held captive in the Monotoli building. If you go there, though, nobody is talking. So you should head to Jackie's Cafe, where Monotoli has been rumored to hang out sometimes.