I can only offer some information obtained from two references I have recently come across when looking for answers to a similar question. Unfortunately, I am neither a Semitist nor an Afrasianist, hence my understanding of the issues is probably imperfect. In spite of this, here is what I have found so far.
Let me begin with a few quotations from an interesting dissertation by Simpson (2009), available here as a PDF (emphasis mine), such as this one (p. 5):
The system of root-and-pattern morphology incorporates elements of phonology and syntax. Morphology in general holds a position between these two domains and as a result reflects the results of changes originating in both domains. The unique properties of Semitic morphology exhibit the results of changes from many different domains including morphologically specific ones. Understanding the processes in morphology, syntax and phonology and how they have contributed to this unusual system of word formation provides important insights into the patterns that occur and those that do not. While the patterns and configuration of Semitic morphology are unique, they reflect processes and underlying mechanisms which are not by themselves unusual. These changes rely on basic phonetic and cognitive mechanisms, as well as the inherent ambiguities in language and the opportunities these ambiguities present for reanalysis. This principle can be seen as underlying many of the changes in language and more specifically those encountered in this study. The results of reinterpretation may result in cross-linguistic patterns but these patterns are considered here to be the results of, not the driving forces behind, the changes.
Also (p. 9):
From the history of Arabic it might seem that the system of ablaut patterns is characterized by a slow process of decay, whereby the system of non-linear morphology represents the oldest, or even the original, stage of the language with a subsequent break down of the system over time. However, once the Semitic family is considered as a whole, this scenario does not hold up so well. The history of the Semitic language family and its subfamilies includes many cases of patterns being lost, but also many cases of new patterns emerging. Many of the non-linear morphological patterns of Classical Arabic are likely innovations not originally found in Proto-Semitic. The modern history of most Semitic languages is characterized by both the loss of older ablaut patterns and the formation of new patterns, giving us a very dynamic picture of developments in the domain of ablaut patterns.
And further (p. 68):
While many patterns characteristic of the earliest varieties have been lost or become obsolete, there are at the same time a number of new patterns and newly productive forms found in many Semitic languages. The types of processes that introduce new alternations or expand the use of existing patterns are proposed to be essentially the same in non-Semitic languages as they are both in the earliest stages of the Semitic and Afroasiatic families and in later varieties of Semitic.
The author then divides the processes into the following main two types:
- segmentally conditioned alternations (such as long-distance assimilation leading to umlaut-like patterning)
- prosodically conditioned alternations (basically loss/reduction of vowels in certain contexts, changes in vowel quality/quantity due to the placement of stress, with examples from several languages including Hebrew, Maltese, and the Modern South Arabian languages)
I strongly suggest that you read the text to learn more. I'm not a Semitist and many of the Semitic-specific details are difficult to comprehend without a proper Semitist background, but otherwise the linguistic reasoning seems rather sensible most of the time.
The author himself admits that the ultimate origin of all of the patterning is currently not discernable, but assumes - and I tend to agree - that there is no reason to think it was very different from what we know of the later history of the family and its individual daughters.
Now, as far as Proto-Afrasian or Proto-Afroasiatic is concerned, a concise introduction to the issue can be found in Bomhard's Afrasian Comparative Phonology and Vocabulary (2014:15).[see the note below] Apart from some information on how Diakonoff vs. Orël-Stolbova vs. Ehret reconstructions differ and/or compare, there seems to be some interesting information concerning the reconstruction of Proto-Semitic (e.g. p. 37) and pertaining to the origin of the Semitic "templatic" morphology (p. 39-42), a few lines of which I can quote here as well (p. 39):
There has been much discussion, some of it rather heated, concerning root structure patterning within Afrasian. Until fairly recently, there was strong resistance to look objectively at the data from all of the branches of the Afrasian language family, far too much emphasis being placed on the importance of the Semitic branch alone, which was often uncritically taken to represent the original state of affairs. In the Semitic branch, the vast majority of roots are triconsonantal. It is certain, however, that at one time there were more biconsonantal roots and that the triconsonantal system has been greatly expanded in Semitic at the expense of roots with other than three consonants (cf. Moscati 1964:72—75; Ullendorf 1958:69—72; Militarëv 2005).
And further (p. 40):
Thus, the Proto-Afrasian root may be assumed to have had two forms, either *CV or *CVC. *CVC could be extended by means of a suffix to form an inflectional stem: *CVC-(V)C-. Originally, these suffixes appear to have been utilized primarily as verb extensions. Depending upon when they became separated from the rest of the Afrasian speech community, each branch exploited to a different degree the patterning that was just beginning to develop in the Afrasian parent language, with Semitic carrying it to the farthest extreme.
Hence, it appears that (1) languages such as Classical Arabic have developed the patterning to an utmost extreme, but (2) not only may the system have been much less "extravagant" at the Proto-Semitic stage, (3) it was also much less profound at the Pre-Proto-Semitic or Proto-Afrasian stage, which seems to be supported by both, internal evidence (in the former case) and external comparisons (in the latter).
While I definitely agree with @jknappen's answer in that we don't really know much, an interesting picture is emerging - essentially, one that actually also agrees well with @carsten's speculative proposal.
[Note: Although Bomhard is a Nostraticist, which could be discouraging to quite a lot of people, references are almost exclusively restricted to Semiticist and Afrasianist literature, with the exception of the Introduction and/or Appendix.]
