That's an interesting and complicated question, amun.
I think perhaps the best way to go about answering it is to appraise the relative merits of the main arguments for the proposed Afro-Asiatic (AA) urheimat/original homeland.
First, Afro-Asiatic is suggested by some scholars to have originated in the Horn because that is the region that today has the phylum's highest diversity. That is, the Cushitic, Semitic and Omotic branches of AA are all spoken indigenously here, whereas other areas host at most two sub-families.
This is a flawed assumption, however, because it heavily relies on the dubious presupposition that Omotic (OM) is an Afro-Asiatic language phylum. In actuality, as explained in
Sands (2009), recent work such as
Theil (2006) has omitted Omotic altogether from Afro-Asiatic and assigned it to its own separate language family based on the observation that "
no closer genetic relations have been demonstrated between OM and AA than between OM and any other language family". This is in keeping with earlier classifications by Newman (1980) and Diakonoff (1996). It is also supported by genetic data, which shows a marked difference between the representative Omotic-speaking individuals in Ethiopia and their Hamito-Semitic-speaking counterparts, in turn suggesting a language switch from Nilo-Saharan to Afro-Asiatic at some point by the Omotic groups of southwestern Ethiopia (an area that borders Southern Sudan).
"A clustering of Ethiopian groups was observed when using principal coordinate analyses with genetic distances, appearing midway between a West African Niger-Congo speaking group (Igbo of Nigeria) and an Indo- European speaking group (Greek Cypriots). Some south-western groups (e.g. Anuak) showed greater similarity to West-Africans while the culturally influential Amhara were more similar to Europeans."
dienekes.blogspot.com/2009/09/more-ashg-2009-abstracts.html
Altogether, this implies that only two Afro-Asiatic sub-families, Cushitic and Semitic, are actually spoken as a mother tongue in the Horn.
But even here, the argument still relies on the assumption that the Ethio-Semitic languages spoken in the Horn evolved in situ in the region, whereas robust
linguistic data in combination with the local presence of the Semitic-associated paternal haplogroup J and Sabaean inscriptions all point to the later introduction of Semitic languages by migrants from the Arabian peninsula. That leaves just Cushitic as the only branch of Afro-Asiatic with a plausible origin in the Horn.
Aside from the respected linguist Roger Blench, it likewise does not help that proponents of the circum-Horn urheimat for AA are researchers like Christopher Ehret (who has issues with Hamitic people; see the
Anti-Hamitism in academia thread).
Ehret also includes root words for "goat" and "sheep", among other things, in his reconstruction of Proto-Afro-Asiatic (PAA). However, such ovicaprids were not yet introduced into Africa from Eurasia at the time of PAA (~10,000). There are
cave paintings that were also recently discovered in northern Somalia which depict a human figure on horseback, one of the earliest such depictions i.e. a domesticated horse. That rock art, which is attributed to pastoralists, dates back to only about 5,000 years ago, whereas the oldest
evidence of horse domestication dates back to 9,000 years ago and is now found in Southwest Asia (no longer Central Asia) -- the exact region where the Hamites are suggested to have crossed into Northeast Africa from.
Besides the above, there's also the fact that all of Afro-Asiatic's most closely related language families are spoken outside of Africa. The hypothetical Out-of-Africa exodus(es) cannot be invoked to explain this discrepancy since proto-Nostratic and proto-Borean are believed to have evolved tens of millenia after that putative migration(s) into Eurasia is proposed to have first taken place.
The predominant autosomal DNA component that unites all of the various Nostratic-speaking communities likewise is Eurasian in structure, not Sub-Saharan.
From the above, the bulk of the evidence therefore suggests the introduction of the Afro-Asiatic languages into Africa by what was likely several waves of West Eurasian migrants (whom we have termed "Hamites" here for convenience).