You could try using ley lines or following bird migrations. That would be different, and it would fit for a culture without a compass. If the islanders trace migrations of other life forms, also- like whales or something- you could try that too.

I don't know how much traditional island peoples use cardinal directions in the Pacific, but in an environment where it is daylight so many hours and twilight is so brief, stars would be an obvious choice as well; to that end, you could render the constellations across the map and treat destinations as additional stars placed on the ocean. I don't know how you could distinguish between them (depending on the undecipherable script, perhaps), or if you would assume the navigator can do that without special marks. That could tie into intrinsic meaning for certain islands.