The dungeon: go north at the townsquare and turn right at the tourist information and then keep walking to the right. There are three caves (did I say dungeon?). Since you've got all star shapes you must have been there. To open the rock, look in the cave on the left. In the back (where you used the cane) you can read a hint.
If that doesn't work out here's the solution:
If that doesn't work out here's the solution:
Spoiler
Statues in the middle cave from left to right: up, down and middle, so use the right statue once and the left statue twice.
[close]