Since CO is so lethal, I guess it could be very fast. Since CO signalling is involved in epigenetics (methylation), it means it could be even one generation, with a bit of luck.
Both those points are reasons why I don't think it would work.
It's
so lethal, when it is a factor, that it doesn't leave much room for a chance (pre-)adaptation squeaking past such a life-limiting emergency.
For (some of) the very first generation to have the means to ascend above the danger that kills their (un-preadapted) cousins means a
very fortuitous point mutation (squared or cubed if multiple SNSes are required to implement this 'skill' from scratch, out of nowhere). It'd be like the X-Gene (of the X-Men universe) spontaneously being useful 'all of a sudden'.
Which is not to say it
didn't happen (the chances of something having happened, that did happen, is 100% by retrospect even if it was unlikely to have happened at the tradutional point of measure of
before it did) and you mention the bottlenecks...
Maybe one of the bottlenecks was a small group of X-Cavemen having the innate ability to avoid monoxide poisoning that claimed their 'normal' fellows.
However... While undoubtedly there were deep-caving 'cavemen' (Rouffignac Cave apparently had cave painters operating at least half a mile into the ground, with or (probably) without much in the way of torch-light, never mind big fires), there does not seem to be the the evidence that this was the norm for the paleolithic peoples (from maybe half way to just a quarter of the way back in time through to the arising of the first anatomical humans. And evidence that they were fishing (presumably outdoor fish, rather than cave fish, regardless of the fresh-/saltwater distinctions) suggests they'd not exactly gone full-troglodyte.
A cave (shallow cave, or just an
entrance to a larger system whose mysteries they explored only relatively briefly/ritualistically) might have handily sheltered them, but it seems we still retain much of our evolution upon the plains,
maybe features from our theorised Aquatic Ape phase, but cave-adaptation (in Dorfy or RL cave-ecosystem terms) doesn't feature much.
Our eyesight is keyed to nocturnal-at-a-push levels of ability, but retains certain expectations of daylight. Our stance isn't squat for avoiding low rocky rooves above our heads. Our skin is atuned to (varying degrees of) sunlight upon it. We're basically not Gollums or Dwarven or Trollish (given that we can recognise those types as being hypothetically more 'of the subteranean life' , and no reason to believe that we
were significantly more like that (perhaps our Neanderthal distant cousins and illicit ancesters push the limit in that sort of direction? But barely).
And, as you point out, we do
not detect CO properly. If the X-Gene for CO detectiom bred itself in due to need, then it reqlly ought to have not bred itself out again without an opposing selection, so easily. Mere non-use doesn't rust an allel frequency. If it was problematic, maybe. And if there were (after avoiding the bottleneck, due to not being cave-humans) more dominant norm-genes bred back over this circumstantially lucky X-Gene (recessive, but somehow was still spread around enough to get the first generation of CO-exposureds out of danger).
Probably it's more complicated than that. Without checking any proper research about anything you've said about what we have already¹ I'd say that maybe the recepter
is a chance thing. That hasn't yet found a connected-up use because most people who experience CO to lethal levels die (by definition!) withoutmanybody having also lucked upon the necessary biofeedback loop to make use of such biophysical self-awareness of the issue and biomechanically/hormonely/neurologically act with the suitably life-afirming response method.
I shall find time to see if I can't find something to educate me better on this subject. Including correcting any misapprehensions that I've succumbed to along the way and misassumptions I've therefore fallen into the trap of.
¹ I 'know', but would need to check that this isn't a Lie-To-Children, that our
haemoglobin acts as a receptor to CO, in exvlusice preference to Oxygen, and that's the problem! I hadn't heard about any further molecular signalling that goes on. Only the ability to diagnose one suffering from CO from their changed appearance in blood-filled areas of the face, like the lips.