The dispersal of the Indo-European language family from the third millennium BCE is thought to have dramatically altered Europe’s linguistic landscape. Many of the preexisting languages are assumed to have been lost, as Indo-European languages, including Greek, Latin, Celtic, Germanic, Baltic, Slavic and Armenian, dominate in much of Western Eurasia from historical times. To elucidate the linguistic encounters resulting from the Indo-Europeanization process, this volume evaluates the lexical evidence for prehistoric language contact in multiple Indo-European subgroups, at the same time taking a critical stance to approaches that have been applied to this problem in the past.
Part I: Introduction
Guus Kroonen: A methodological introduction to sub-Indo-European Europe
Part II: Northeastern and Eastern Europe
Anthony Jakob: Three pre-Balto-Slavic bird names, or: A more austere take on Oštir
Ranko Matasović: Proto-Slavic forest tree names: Substratum or Proto-Indo-European origin?
Part III: Western and Central Europe
Paulus S. van Sluis: Substrate alternations in Celtic
Anders Richardt Jørgensen: A bird name suffix *-anno- in Celtic and Gallo-Romance
David Stifter: Prehistoric layers of loanwords in Old Irish
Part IV: The Mediterranean
Andrew Wigman: A European substrate velar “suffix”
Cid Swanenvleugel: Prefixes in the Sardinian substrate
Lotte Meester: Substrate stratification: An argument against the unity of Pre-Greek
Guus Kroonen: For the nth time: The Pre-Greek νϑ-suffix revisited
Part V: Anatolia & the Caucasus
Rasmus Thorsø: Alternation of diphthong and monophthong in Armenian words of substrate origin
Zsolt Simon: Indo-European substrates: The problem of the Anatolian evidence
Peter Schrijver: East Caucasian perspectives on the origin of the word ‘camel’ and some notes on European substrate lexemes
Borrowings sometimes do displace native words, even ones with a similar meaning. English for example has plenty of pairs like owndom/property, blee/colour, selfhood/identity, where the native word is mostly gone.
Plus it's possible that Common Slavic didn't have a word for the specific type of pigeon that was being called "columba". Latin itself made a big distinction between those columbae and the wood pigeons, called "palumbes"
If that's correct, my bet would be on some pigeon/dove found near the Mediterranean coast. Potentially rock doves; note how the native range (dark red) is considerably far away from the Slavic urheimat.
Then later on semantic widening can easily make the word for a specific type of pigeon become a generic word for pigeons.
Regarding when this would happen, it would be:
For reference that would be roughly when Late Latin splits into the Romance languages, traditionally dated around 600~800.
About Holzer's hypothesis: frankly I think that the Temematic hypothesis is worth exploring, but most things relying on Temematic can be easily explained without it, thus being a bit more parsimonious. I'm not too informed on specific Slavic developments though, so take what I say with a grain of salt.
A third possibility would be that OCS and other Slavic languages got it from Greek instead. I find it implausible because Greek shifted /u/→/y/→/i/, so the second vowel would be something like *ę or *ь (front) instead of *ǫ (back).
English has a very, very specific sociolinguistic history that has resulted in such deep changes in the lexicon. The relationship of early English towards Romance languages is very different from early Slavic towards Latin/Romance.
Personally what I find the most convincing part of your argument is the map of the native spread of the pigeon. I still would find it odd that the word would be loaned either in the early period that you propose (no apparent practical need for such a word to be loaned, esp. considering the spread of the species, it simply wouldn't be needed for the Slavs).
I picked English for the examples due to the amount of those borrowings, but the general process happens in other languages, in different situations - even without the whole class association between Anglo-Norman and English speakers.
Other two examples that I can mention of the same process are in Portuguese:
1. Basque ⟨txakur⟩ pup, cub → Portuguese ⟨cachorro⟩ puppy or dog (dialect-dependent meaning). Initially the borrowing displaces the native word ⟨cadelo⟩ puppy, from Lat. ⟨catellus⟩; then in some dialects it gets widened to refer to any dog, thus also displacing ⟨cão⟩ dog, from Lat. canis - with ⟨cão⟩ becoming a formal word. The process is specially obvious because the feminine ⟨cadela⟩ is still widely used.
2. English ⟨bacon⟩ is clearly replacing the native ⟨toicinho⟩~⟨toucinho⟩ in Portuguese, even if both refer to practically the same pork cut containing both meat and fat, typically cured and often smoked.
Romanian also has a rather relevant example: it did not inherit Latin ⟨columba⟩, and yet it borrowed ⟨hulub⟩ "pigeon" from some Slavic language; potentially Ukrainian.
If the borrowing happened as early as 500~600, the motivation could be contact with that species of bird. It's worth noting that Common Slavic expanded further into the region than the modern range of the Slavic languages hints - it goes as West as a good chunk of what's today Austria.
And, if the borrowing happened in later times, like 900 or so, it could be motivated by religious significance.