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
I don't have much to add to your comment, since my knowledge of historical linguistics is still limited and focused on Slavic languages. I just saw this on reddit and found it interesting (esp. the first two articles, which I've only skimmed for some interesting remarks for now). But still, I must say I find the idea that Slavs would adopt the word for the pigeon from the Romans a bit odd. Would they really not have a native word already, and why would it specifically be the Romans that they got the word from? It would certainly have to be loaned very early on, as it is used across all Slavic languages, it's not just OCS; possibly it could have been mediated through Germanic (as was e.g. *Rimъ = Rome).
G. Holzer has proposed that it was loaned into Slavic from "Temematic", an extinct substratum language that was supposedly the source for a number of Balto-Slavic words related to farming and similar activities, and which (among others) underwent PIE *k > *g, thus explaining the g-.
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.