Not even African languages in general: clicks seem to have originated only in the Khoisan language "family" (*), and spread from there into neighboring languages. In other words, clicks don't seem to be an African feature so much as a Khoisan feature.
As for why they're only a Khoisan feature—it really seems to be pure random luck! Clicks appear paralinguistically, as you mention, and also show up in twin-codes, showing that they're not that difficult to come up with.
But for the most part, languages gain new consonants in two different ways: either an existing sound shifts, or bilinguals borrow a sound from one language into another. For example,
/ð/ was added to Greek and Germanic when stops lenited, and to Swahili via overlap with Arabic.
Click consonants are borrowed fairly easily, which is why they're found all across southern Africa even though the Khoisan languages are rare and dying. (And why they're steadily moving up the east coast now as well!) But there just aren't any common—or even attested—sound changes that can create clicks where no clicks were before.
How Khoisan got clicks in the first place is lost to the mists of time, farther back than the comparative method can reconstruct. Maybe
t → ǁ is a sound shift that happened, but it's so rare and unlikely that it only happened once in a surviving language. Or maybe language was invented independently in several places, and the version created by the pre-Khoisan-speakers just happened to include clicks while others didn't. There's unfortunately no way to know for sure now.
(*) The Khoisan languages don't seem to be a family in the same way that the Germanic languages or the Romance languages are. Rather, they're a collection of scattered languages grouped together for convenience; they all share some features, but there just isn't enough evidence to say if that's due to a genetic relationship, a sprachbund, areal features, or even just coincidence.