A Myrddraal wrote the Dark Prophecy on orders, as a threat. I might want to use some of the reasons, so the rest on that is RAFO. Fain (now amalgamated with Mordeth) was seeking his own power base, something he would try again with Pedron Niall and Toram Riatin. He wanted enough power to be able to kill Rand, Mat and Perrin, though most especially Rand, and to protect himself against agents of the Shadow. Because of Darkfriend reports, the Myrddraal who wrote the prophecy already knew who the strangers on Toman Head were, or claimed to be: Artur Hawkwing's armies returned to reclaim the lands stolen from Hawkwing's heirs. He knew that they collared women who could channel, which appealed to Fain/Mordeth, since one disliked Aes Sedai at best and the other purely hated them. The Myrddraal didn't simply give this up to Fain, you understand. Fain is one of the few people who could successfully torture information out of one of the Eyeless. As for why he went to Cairhien first, he knew the location of the Waygate there (along with several others and how to read the guidings in the Ways, this last from Mordeth) and preferred to use the Ways rather than make the longer cross-country journey from Fal Dara to Toman Head.