How about we leave the dark powers out of the discussion? They are irrelevant to it beyond the fact that "we made them willing" to deliver PCs on the island.
On building ships. Building a cog or a caravel, as would be required to travel to Tejeda, was no small feat and a full time job of its own. It required specialized training, skilled labor, a shipyard, massive resources, permissions from local authorities, and lots of time. Shipbuilding is not a skill that would make much sense to give to PCs within our module.