The Devil King's Palace doesn't open the cave you are talking about, but it does contain an empty chest with a prayer in it about death being great or something -- it is on the bottom floor of the main castle in a room to the left of where the teleporter drops you. You need to have learned that prayer to fight the bonus boss in the cave you mentioned and it drops the only Death Fragement in the game, which you need to make either the best bow or mage ring in the workshop.

The cave itself requires you having beaten the second boss in the thief cave, so if you haven't been back there in a while there should be a new boss hiding at the back where the bandit leader was. If you don't have the cave open there is a woman in the bottom left house in . . . Stanely, I believe it is (the left of the two), and she should mention monster activity in the thief cave and add it to your map. After clearing it out the second time you can talk to her again and she should open the second cave -- she might even open it the first time you talk to her if you are late enough in the game.