The lost tomb is south of the mysterious cave, but you'll have to go around the eastern end of that mountain and turn west into the channel (ie head south west from the harbour). The cave entrance is fairly low, though not right down near the water, and shouldn't be too hard to spot on your left as you get into the channel (or on the right if you are heading towards the harbour).
I don't recall having to do anything special to get access to the mysterious cave. Once you go through, meet Bellegar and go though his trials, the door does get locked, so maybe you just went though there earlier?
