Chronicle III, Page 53:
“Thrall and his people took refuge on a nearby chain of islands. The clouds eventually parted and the seas calmed. The Alliance navy was nowhere in sight, but that did little to ease Thrall’s anxiety.”
So the Alliance fleet lost the Horde fleet in the storm.
Followed by:
“The days ahead were not easy for Thrall and his people. They found themselves fighting enemies old and new. The storm had blown part of Daelin Proudmoore’s fleet to the islands, and humans had fanned out across their shores.”
So the Kul Tiran forces they fought on the Darkspear Islands weren’t being led by Daelin; they were a fragment of his armada, blown off-course by the storm as they had been. Daelin himself was with the main fleet.
And for him to have subsequently learned of Lordaeron’s fate and gone off in search of survivors, he had to have returned home to find out about the Scourging and the fact that Jaina had taken a fleet to evacuate them.
Attacking the Horde became a priority again when he discovered the Horde still existed in Kalimdor, upon arriving there. Prior to that, he had no way of knowing they had made it through the same storm that had cost him part of his own fleet.
And yes, he then prioritized destroying the Horde ahead of finding Jaina, because he was just that fixated on revenge against the orcs. Plus as soon as he found and occupied Theramore he’d have learned Jaina was alive from the inhabitants, satisfying that goal, as he took over the place while she was away with Thrall trying to figure out what was going on with the trap set to kill Thrall.
The first thing we saw in-game was him attacking the Horde not because that was the original reason he’d come, but because as soon as he arrived in his search for survivors he saw an entrenched Horde and prioritized their destruction instead.
Moreover the in-game books aren’t contextualized as being from a biased source; since Vanilla they’ve basically amounted largely to more detailed exerpts from the game manuals and a few summaries of events from the novels, containing details spread across multgiple POV’s that no single source in the lore could have known to include them in the same aggregated account.
Chronicle III, Page 111:
“Though the Horde and the humans of Theramore Isle maintained peace for years, it did not last.”
Chronicle III also establishes here that years had passed between WC3 and the Founding of Durotar campaign, so it would make little sense for Daelin to have still been puttering around at sea for that long looking for the orcs straight off the disastrous pursuit into that storm. He was looking for survivors of the Scourging, meaning he had to have gone back and found out the Scourging happened, as WC3 didn’t have the late WoW-era precedents of magical trans-continental communication, and in fact numerous plot points throughout it are dependent upon that not having been possible at that time.