How many thousands of years roughly did it take humans to go from cave drawings and making clicks, whoops and coughs to communicate to having things like parts of speech, consonants, spelling etc.?
The simple answer is that we don't know. Our first really reliable clues about ancient languages only appear with writing, with the oldest language known in detail being Sumerian, from over 5,000 years ago.
We can attempt to reconstruct older languages by comparing their modern descendants - features that most modern descendants have in common probably appeared in the common ancestor language. We can get interesting clues about history from such language evolution. For example, it's one of our major sources of information on the past movements of peoples (the others being archaeology and genetics). Noting whether related languages use similar words for farming-related terminology, or wheels, etc., tells us whether these technologies were probably in use before the language split into its modern descendants. Such reconstructions of ancient languages are tentative only, since there's a certain amount of guesswork involved. The oldest thought-to-be-reliable reconstruction like this is probably Proto-Afro-Asiatic, with the language dating to about 15,000 years ago.
More generally, we can look at the rate of evolution of languages (estimated from differences in related languages), and estimate the time at which modern languages would have diverged from each other. One such study
put the possible ancestral language at about 300,000 years ago (see figure 3). Note that the uncertainty in these dates is large; the error bars in figure 3 are about +/- 100,000 years. The extreme possibilities are as recent as about 100,000 years ago, and about 500,000 years ago. The estimate of 100-300,000 years ago for the origin of language agrees with those who believe that language developed with early Homo sapiens. Some people suggest that language was already developing in Homo erectus (about 1.8 million years to about 100,000 years ago). The anti-Homo erectus had language arguments generally come down to:
Hyoid bone (which supports the tongue): less effective shape for speech, and lacks the muscle attachments needed for control. The oldest modern-type hyoid bone found so far is a Homo heidelbergensis (the intermediate species between H. Erectus and H. sapiens, about 500,000 years old.
Cultural sophistication. Homo erectus appears to have had much less use of symbolism in their culture. Some possible ornaments have been found, and body paint might have been used, but such things were much less common than with later Homo species.
The pro-Homo erectus had language arguments:
The late evolution of Homo erectus, with evolution of the hyoid bone, and increase in brain size, might have been driven by the development of language.
Cultural sophistication: Homo erectus crossed substantial water barriers in their settlement of SE Asia (e.g., to cross to Luzon about 700,000 years ago). Such water crossings would have required boats or rafts, and planning.
This is the point where it is difficult to answer your question: how long did it take to go from "proto-language" to complete languages? If Homo erectus used a proto-language, and complete languages only developed with early Homo sapiens (or H. heidelbergensis), then the step from proto-language to language might have taken about 1.5 million years. If Homo erectus developed language, then the step from proto-language to language would have taken place at some unknown time in that 1.5 million year interval.
What we do know is that by the time we have any concrete evidence of language, human languages appear to be fully-developed complete languages. For example, Australia appears to have been settled by people using complete languages (and building boats, doing art, with a complex culture, etc.), perhaps by 60,000 years ago. Perreault & Mathew (2012), cited and linked above, place the origin of language with early Homo sapiens in Africa, in which case the spread of Homo sapiens around the world would have spread the languages of Homo sapiens around the world. Their result doesn't rule out the use of proto-language or complete languages by Homo erectus - as Homo sapiens spread around the world with minimal genetic exchange with Homo erectus, there could have been an accompanying lack of exchange of languages.