While on Heaven Cent quest you use the rusty key on door at bottom of Shak Maze and you can obtain this from one of chests there which they are not treasure or coffer chests. No key is required to open them either.
Here is the currect Directions of each Star
Odin - North.
Titan - South.
Shiva - East.
Leviathan - West
Alexander - North-East
Ifrit - North-West