1. Thais, then take the boat to Carlin (Svargrond if you also buy enhanced blessings)
2. Carlin, then take the boat to Ab'dendriel
3. Ab'dendriel, then take boats to Eremo (go via venore to Port Hope if you buy enhanced blessings)
4. Eremo, then steamship from Cormaya
5. Save Kazordoon for last, since you can go via the shortcuts from the steamboat, this way you save yourself the painful walk into kazordoon from ab'dendriel.
The 2 new blessings involve a lot of walking, so they will take up loads of time whenever you choose to buy them, but you can reach Edron from Port Hope, so maybe that one before Eremo. And you can reach Svargrond from Carlin & Thais, so perhaps go from Thais to Svargrond and then to Carlin, in order to avoid going via Venore.
The variations in different paths are quite small since most of the travelling is done via boats. But I believe this is the most efficient way to go since it only involves one trip via Venore.