This was a fun navigation puzzle. I love when RPGs give simple directions like "west" or "southeast" and the journey turns out to be longer and more complex than that implies. This gave me a similar feeling. At first it felt like the game was just leading me from town to town, but it was exciting when I reached Soraion after Mezuris and Soraion didn't have a pointer to a new place.
My route was: Faules, Yustepa, Mezuris, Soraion, Balbalap (this seemed just barely possible to reach), Luwoll, Valdivia. Maybe the intent was to go back to Mezuris and sail to Hetra Bheb, but instead I wanted to just go off on my own and see if I could find anything east of Soraion.
I feel like I solved the "final puzzle" by accident. If you follow the directions from Luwoll to the letter, you drown before reaching Valdivia. I guess the intent was to think about what those directions are telling you, and realize that you can take a shortcut by going directly east. I didn't realize this, and just decided to go east on whim, and stumbled on Valdivia, which made things a bit anticlimactic.
I also didn't find any kind of HP-restoring item....