Freeing the Runaway Five
On the way across the bridge to Fourside you will be stopped and given a Diamond. Looks like something that could be useful in freeing the Runaway Five from their predicament once again! Head to Topolla Theater and talk to the manager there. Once the Runaway Five are free, they'll play one last show. The Department Store has opened up finally, so head on over there!
Enter the massive store and head upstairs to the different floors to check out the goods. You'll want to buy Gold Bracelets and Coins of Defense for Ness and Jeff. Also, buy a bunch of Big Bottle Rockets for Jeff and Teddy Bears for Ness, as you will need them. Do not buy Paula anything! You will see why shortly. Give Ness or Jeff the Franklin Badge if Paula has it. When you are done preparing, head to the exit of the store and the lights will go out. When they come back on, Paula is gone!
Make your way upstairs being very careful around the monsters. The enemies here are extremely tough. If you stocked up on Big Bottle Rockets, then fire one off if you are attacked by multiple enemies at once. Make sure you save one for the boss battle coming up. As you reach the top floor, you will come across the Department Store Spook.
The Spook gives you a clue as to Paula's location. "Monotoli". If you visit, you won't learn anything special there, and will need to explore the city to continue. If you either search or check with the hint man, you can learn the next event is at Jackie's Cafe, located in the north-west area of the city.