Go back, eventually get the fortune that makes you go to a new town. You'll see a key high up on a ledge. Talk to someone enough times (but not too many times) so you can grab the key, then you can go back to the Belome statue and give it to him. The treasure room's optional, so no biggie if you don't do it, but it certainly helps.
More direct explanation:
Get the fortune that takes you to Monstro Town. In one of the doors, you'll see a Thwomp near the back of a room. Talk to him a few times, I forget how many, like 4 or 6. Each time you talk to him, he'll slam the ground and the key will inch further near the edge of the platform it's on. So keep checking outside when you talk to him. Eventually the key will fall to the ground where you can grab it. But talk to him too many times and the key will inch off the edge of town, gone forever.