Once you return to the castle, return the last scroll to the sage. You should then speak with the king, as well as the princess who hands you a very valuable item, the Heal Ring. You will automatically regenerate health while this ring is equipped. Before you get going, make sure you have a set of Needles in your inventory, you'll need it when you reach Baal's castle. When you're ready, make the short journey to the sword shrine east of the castle.
Sword shrine
First floor
Assuming you have obtained and utilized all three sword jewels, step into the shrine and Look at, or even Talk to, the sword in the stone. The Star Sword will speak with you and congratulate you for restoring its power. It will tell you to have faith in it, and never release it even if you are close to death. When you are done, you will step into the actual dungeon of the shrine.
The shrine dungeon is three floors deep, and you must travel through it to reach the outside of Baal's castle. On the first floor, you have a couple of objectives, including finding the Red Key which is needed to open the door that leads to the second floor. Along the way, you should attempt to locate the God shield, the best shield in the game.
When you arrive on the first floor, you will see a mirror on the wall of the hallway below you. This mirror, and all those like it, will spawn a clone of your character. These clones are immensely powerful compared to all of the other enemies that you will encounter from here to the end of the game, and you are highly advised to avoid the clones at all costs. However, there is one kind of enemy you should seek out. The enemy that changes shape when you get close to it has a high tendency to drop Jet potions when it gets defeated. Try to fight as many of these as you can to fill the empty spots in your inventory with these powerful potions.
At this point, you should equip the Star Sword. If you actually check your stats, you may notice that the attack power of this weapon isn't quite as good as you might have expected. It's actually quite poor. However, you should follow the swords advice and keep it equipped. In fact, you should actually allow yourself to be killed by the enemies. If you are killed while holding the Star Sword, you will be instantly revived, you will automatically advance to the next level (unless you're already at level 40), and the true power of the Star Sword will be unlocked. (Please note that the sword will only revive you once. After the sword's power is unlocked, if you die, you must continue as usual.)
From the dungeon entrance, you should head south, and continue walking south, ignoring the passage containing the mirror. Keep making your way down, through a narrow hallway. After going south from one chamber, head east into a large vertical room. Walk down to the bottom, near a pool, and investigate the lower right corner to find a hidden chest which contains the God shield. Then return to the previous room, and travel generally south until you reach a small room. Inside this room is another hidden chest which holds the Red Key.
Once you have the Red Key, you must return to the entrance of the dungeon, way back at the top. Now you must pass through the hallway containing the mirror. Again, ignore the clone that appears, they simply do too much damage. Walk to the right and then head down. Before you reach the door, you can examine the small chamber to the left, where you'll find a hidden chest. This chest contains the best race-specific weapon which you may have already obtained in the Holy Land, and is not as strong as the fully restored Star Sword. Travel down the hallway that leads to the door, and equip the Red Key in order to open it. Then take the ladder to the second floor.
Second floor
You begin in near the upper left corner of a very maze-like chamber. Your goal is to reach the girl and the treasure chest in the upper right corner. To reach it, you'll have to travel down the center of the chamber, along the bottom to the right, and then all the way up the right side where you'll reach a door. The door can only be unlocked by the Blue Key, and you can obtain one of them by defeating one of the tall enemies that patrol the floor. Once you get a key, open the door and speak with the girl. She will thank you for saving her, tell you how the dungeon connects to the underworld, and insist that she will be able to make it out on her own. Open the chest to the right to get the Silver Key, which you'll need to escape from the third floor.
Now head back to the bottom, head left, up the center, and make your way to the lower left corner which contains a passage to the left. There is another mirror in this passage, so beware of the clone that appears. Take the first path south, and head left from the next chamber. You'll reach another long vertical room with a hidden chest near the bottom. This chest contains the God armor, the best armor in the game. Be sure to equip it immediately. Then head back up, and walk right, across the previous chamber and over to the opposite side. Then head south to reach the ladder that leads to floor three.
Third floor
The third floor is a bit different from the other floors in that it has two hallways that "wrap around" to the opposite side, allowing you to travel in an infinite loop if you continue to follow particular paths. There are a number of hidden treasure chests to discover on this floor, but none of them offer anything better than what you should already have. Many of them contain gold, and you're not likely to need much more than what you already have.
Since the passages wrap around, there are a number of ways to reach the exit from this floor. However, this walkthrough will provide the shortest path. From the second floor, take the passage to the right past another mirror. Then take the north passage out of the next room. From there, take the long passage to the right. Continue right when you reach a fork in the passage. Once you're in a new room, walk south continuously until you reach another door. This is the door that requires the Silver Key which you obtained from the chest next to the girl that you rescued on the second floor. Equip the key, open the door, and walk down to the ladder that leads out of the dungeon.
The underworld
When you escape the dungeon, you will arrive at the very bottom of a long maze. The maze leads to the entrance of Baal's castle at the very top. There are several paths to take, and there's no one absolute path that you must take to reach the entrance. That being said, more paths lead to dead-ends than not. The entire left side of the maze is almost entirely full of dead ends except for one passage that leads you back to the center. In general, you should stick to the right side of the maze as you ascend up the screen. Even if you take the right side all the way to the top, and reach the dead end there, it's a simple matter to walk back down the left side and rejoin the center of the maze, which will lead you to the entrance. Naturally, the enemies that you face here will be quite strong, but if you're wearing the God armor and shield, you shouldn't take too much damage. The Heal Ring should help repair what little damage you sustain.