The princesses have been relocated, so the bros have to chase after them. Go south to reach Doop Doop Dunes. A Toad near the Lakitu Info Center says to drop down the cliff, then go straight to reach Twinsy Tropics. Nabbit is at the base of the cliff. Try to talk to him and he burrows underground. Go near him and return to the surface to bring him back to the surface, along with the Dropchopper Bros. Attack. There are Spikes here. Go south, then southwest to reach the Toad Village. Going due south won't get you very far.
In the Toad Village, there's a pensive Toad. He says they know where Nabbit is, but they're not fast enough to catch him. Agree to help and you'll find Nabbit, who can create a temporary double of himself. You have four minutes to catch him. The double will flicker, so you can tell the difference. Catch him three times, each with more doubles, and you'll get the Bros. Attack Cannonball Chuck. Once you're done gearing up in the Village, go east. There is an oasis here. Try to go east and someone calls to you. It's the Paper Goomba from before, who gave the bros the Battle Cards. The bros don't recognize him. He wants to tag along on the journey to Bowser's Castle. Mario refuses. The Paper Goomba doesn't take "No" for an answer. He and Starlow argue about his presence. Things eventually calm down. Go east.
There's a warp pipe here. Use it to unlock it. Cross the other bridge and the ground starts shaking. Starlow thinks it's a papercraft initially, but she realizes the truth isn't much better. It's a ton of Chargin' Chucks. They'll initially charge at the bros in pairs. Jump to dodge and they'll hit each other, knocking off their helmets. They'll also throw footballs. Use the hammer to counter. After a while, they can summon more allies to help them, so clear them out quickly. If keeping all three bros alive proves difficult, it may be easiest to fight the battle with only Paper Mario. The Chargin' Chucks will only charge at you, which is easy to dodge with Paper Mario's floaty jump. Go south to Twinsy Tropics.
Tunnel under the cardboard platforms to get past them. Go east and Starlow notices some new paper terrain that could take them someplace new. I returned to Toad Village to find the Toad with the quiz and found a warp pipe here. Follow the path to the pipe that leads to the dungeon and the Paper Goomba will confirm you're headed in the right direction. From the dungeon, the bros can sneak through the back door of Bowser's Castle. Inside the dungeon, he says they need a red medallion. The bros show it off and he wants to take a closer look at it. He then shouts out that they're in the dungeon. Two Fire Bros appear, noticing the medallion for the gate to the castle. They're happy to have it back, as the bros could do some serious damage with it. Starlow states the obvious, calling the Paper Goomba a backstabber. He prefers to think of himself as a master strategist. His goal was Bowser's forgiveness. He thinks a promotion is possible. He leaves and Starlow says they have to get the medallion back.
The bros have to find the enemy with the medallion. Defeat Fire Bros for hints. The hints you're given are random. Stay healed. When you find the Fire Bro, defeat it and it'll surrender the medallion. Starlow tracks down the Paper Goomba, saying he'll pay for double-crossing them. He runs off and she chases, but the bros just want to deal with Bowser.