Okay, I didn't hunt down the city, but I put ashore where there is a deserted cabin and a temple, with the ocean on the east side of the land, just like the map. I figured I'd let it up to you to find it.
You should look southeast of your red X on the opposite side of the Yucatan peninsula.
So sail north of Campeche, around the peninsula, then due south along the coast until you reach that corner between a pirate haven and the town of Lorient.
Do you understand?