Es gibt allerlei Karten über Westeros, ich beziehe mich auf die hier: http://images2.wikia.nocookie.net/__cb20120611150704/gameofthrones/de/images/7/7a/Westeros.jpeg
Die Mauer ist etwa 300 Meilen lang. Bis nach Königsmund über den Königsweg ist es grob gemessen etwa sechs mal so weit, das entspräche dann 1800 Meilen. Wenn Du jetzt rechnest, dass Du mehreren, ausdauernden Pferden etwa 50 Meilen am Tag schaffst, könntest Du die schwarze Festung von Königsmund aus in etwa 36 Tagen, also rund 5 Wochen schaffen.
Ich habe mal ein bisschen gegoogelt, und eine englische Website rechnet etwa einen Monat für diese Strecke (es wurde 1500 Meilen als Längenangabe verwendet).
Nach Dorne (Dorne ist ein weiter Begriff, ich nehme jetzt mal Sonnspeer als Ziel) müsste man etwa vier Wochen brauchen, allerdings muss man dafür die dornischen Marschen durchqueren, sodass man vermutlich etwas mehr Zeit einplanen muss. :)
Wie gesagt, dass sind jetzt nur sehr sehr grobe Schätzungen, aber ich hoffe ich konnte Dir ein bisschen helfen. ;)