Ykhjuy

Suppose anatomically modern, but technologically primitive, humans (say, early Paleolithic) were magically transported to a world broadly similar to our own, but where open flames are impossible. (I don't much care about the mechanism, but if it matters, assume fire is suppressed due to 3-4 times the amount of nitrogen and other inert gasses in our atmosphere; the mild narcotic effects should be taken care of in not-too-many generations of adaptation).

Also presume that there are ways to work around the lack of heat for cooking (e.g. ceviche, which uses acid rather than heat to denature proteins).

Given that anatomically modern humans existed for hundreds of thousands of years of prehistory on our world, is it plausible that a tireless, stone-age civilization could persist for at least tens of millions of years?

Before I give the answer you're looking for, just a word on atmospheric modelling, particularly in respect to fire. I know you're handwaving it for now, but to explain how it works;

The best way to think of an atmosphere is in terms of Partial Pressure. If you think of 1 ATM being 1 Bar, or the pressure of atmosphere experienced on Earth by someone at sea level experiencing average pressure, then the amount of gases we need to survive are best expressed in terms of partial pressure, not a percentage of pressure. So;

1) Humans need between 0.15 and 0.30 ATM of O₂ to survive normally

2) Humans need there to be less than 0.02 ATM of CO₂ and other toxic gases to survive

3) You can add inert gases to taste, remembering that Nitrogen isn't truly inert, so you can only add up to around 2.5 ATM of it before it causes a narcotic effect and can potentially cause other issues with long term exposure.

Add up all the PPs you put into your atmosphere, and that gives you the atmospheric pressure on your given planet. The important point to note here is that if your humans are breathing, fire is possible. The PP of O₂ required for humans is enough to start fires, regardless of what other gases are in your atmosphere. In other words, PP is what counts, NOT %P.

But for the sake of argument, let's handwave that away and figure out how your proto-humans will fare on your fireless world.

To begin with, most anthropologists believe that humans didn't develop their intelligence significantly until they had harnessed fire. This is despite the fact that they had the capacity for many millennia beforehand. Why? Because before fire, they were purely intent on survival. What fire did was give them a safe place to rest at night, and think. Not about their next meal, or what's out in the darkness, but on what they did during the day, what they saw, what patterns they could form out of their observations and what could have possibly gone better.

On a new world, if they're inherently safe (IE no real predators) this might not be as much a factor but if it's similar in safety to ancient Earth (read as not very) then that ability to sit and think somewhere that natural predators won't approach has been taken from them and that could significantly retard their rate of development as a species.

Fire, when you get right down to it, is used for a lot more than cooking. The Aboriginal people of Australia used to use it to clear out brush before summer, effectively back-burning to prevent firestorms during the heat of summer. That's not a problem on your planet per se, but that lack of burning away means that your forests don't have a mechanism for getting rid of excess humus and other debris, like dead trees. This could cause your proto-humans other issues like providing ideal ambush spots for any predators that do exist, and a problem with rotting vegetation infecting usable fruit and vegetables with various diseases. It also means that you lack a key strategy in protecting yourself and feeling safe, knowing that other animals fear fire. This in turn could lead to other strategic hunting methods (like scaring animals into traps) might not happen either. The other use that it had was in tool forming, it being a tempering agent for certain materials.

Could your humans survive without fire? Like you say, there's already compelling evidence that they did. Would they thrive and grow? Perhaps not. The more you want your humans to advance beyond mere survival the less likely it is to happen without fire.

Issues that your humans would face:

Climate: A civilization without access to fire would be limited to areas where they wouldn't need heat to survive a cold climate. This would severely affect where they settled.

Body hair: Connected to the above idea, your humans might have stayed hairier.

From Wikipedia: https://en.wikipedia.org/wiki/Control_of_fire_by_early_humans
"Environment and nighttime activity
The control of fire enabled important changes in human behavior, health, energy expenditure, and geographic expansion...This ability to manipulate their environments allowed them to move into much colder regions that would have previously been uninhabitable after the loss of body hair. Evidence of more complex management to change biomes can be found as far back as 200,000 to 100,000 years ago at a minimum."

Unable to boil water: They would be more prone to waterborne diseases that would have been dealt with by boiling the water. So far more dependent on fresh water sources.

More dependent on other sources of light: The cycle of the moon would be more important since moonlight would be the only way of extending working hours.

From Wikipedia: https://en.wikipedia.org/wiki/Control_of_fire_by_early_humans
"activity was no longer restricted to daylight hours due to the use of fire. Exposure to artificial light during later hours of the day changed humans' circadian rhythms, contributing to a longer waking day.[43] The modern human's waking day is 16 hours, while most mammals are only awake for half as many hours.[41] Additionally, humans are most awake during the early evening hours, while other primates' days begin at dawn and end at sundown. Many of these behavioral changes can be attributed to the control of fire and its impact on daylight extension.[41]

Less efficient tools and weapons: Fire was used to draw our impurities or temper certain types of rocks so they were easier to flake and shape into blades.

This article talks about the importance of fire to the development of early weapons:

https://www.sciencemag.org/news/2009/08/early-tools-were-born-fire
Early Tools Were Born From Fire
Modern humans may have been using fire to make tools more than 30,000 years earlier than once thought, according to archaeologists working in a string of rocky caves along the South African coast. At Pinnacle Point, researchers have found evidence that people began heat-treating stone to make it easier to shape into tools about 70,000 years ago and possibly as early as 164,000 years ago. The find adds to the evidence that a wide range of sophisticated behaviors--from advanced toolmaking to symbolism--were flourishing around the same time."

Socialization: Another issue that's mentioned is the social aspect of gathering around the fire. The wikipedia article I mentioned above stated that contributing firewood for the fire may have been one of the first forms of taxation. Arguably, humans survived and thrived because we developed into social creatures. At the very least, your humans would need a different catalyst to encourage the formation of society.