- SPOILER WARNING
The Castle of Palamecia is situated North of the Coliseum [sic] near the vast expanse of desert. It's in the mountains meaning you cannot enter it by foot. The only way to reach it is via airship, by landing on the castle.
If you meant Castle Pandaemonium, that replaces Castle Palamecia on the world map as soon as it is destroyed. You cannot access it via Airship anymore. Instead you must reach it by making your way through the Jade Passage, the entrance of which is situated on the cape East of Mysidia.