Walk west from the Ocean Palace to return to Nabooru and heal up. Go south from Nabooru and you will see a spider-like monster blocking the path to the south. This is the River Devil that some of the townspeople talk about. Since you have the Flute now, you can press B to play the flute, which will make the River Devil disappear. Now head south.

There are three unavoidable action screens along the path here. Each one includes a fence where red Lizalfos will throw rocks at you. The trick to avoiding the rocks is to stop walking for a moment after they throw the rocks. Or, if you were standing still when they threw the rocks, start walking. They throw the rocks based on where they think that you are GOING to be at the time that the rock lands, so you need to keep changing your pace and location by jumping and stopping. You will still probably have trouble avoiding the rocks. In these screens, you will also encounter orange Lizalfos and a Zora.

After you get past the third action screen, walk southeast along the path that borders the graveyard. There is a cave past the marsh to the north that has a 500 point P-Bag in it. If you continue on the path, you will find a bridge. After crossing the bridge, there is more forest, with a desert to the south. If you go along the east coast of this desert, you will find a hidden heart container. The southeast part of the forest has a hidden action screen with a 50 point P-Bag.

There is a town to the west of the desert called Old Kasuto. However, there is almost nothing there except an old man in one house and a bunch of invisible Moas flying around injuring you periodically. It's not really worthwhile to go there, so just go north from the desert to a cave in the northeast part of the forest.

This cave contains Tektites, an orange Lizalfos and a red Lizalfos. Once you get outside, you will find yourself in a forest. The hidden town of New Kasuto is here. It's in the north part of the forest. There are two squares of forest at the top row. Below the leftmost square, New Kasuto is hidden. Use the hammer next to that square to reveal the town, then go in.

You can heal up and refill magic here. In the first screen, there is an old woman in a purple dress who will let you into the house. Go to the back and you will find a magic container. In the second screen of town, go into the house with the open door and then go into the fireplace to find an old man who will teach you the Spell spell. Finally, go to the third screen of town, which seems mostly empty. Cast Spell. A strange building with a very tall door will emerge from the ground. It contains a Magic Key. You will need this key to get through the next palace, because there aren't enough keys in the palace to unlock all the doors.

The next palace is the Hidden Palace.