It's a bit of a side-step of the question, but there's no reason we need to domesticate solitary cats if all our dogs and wolves are dead. There are plenty of social cats who could be bent to our will.
Lions are one option, but probably a bad one as they're so big. I'd posit that hyenas are the next best option. They're highly social endurance-predating feliforms and fill very similar niches to wolves in their environments.
They're even already well on their way to domestication in places like the city of Harar.
Edit: Thought I'd expand a little on why the other options available are less likely choices, and the thought process that led me to hyenas. Come with me down the rabbit hole!
One of the key reasons that dogs are able to occupy the niche that we have collectively carved out is that they are highly social. Social animals already have pre-evolved mechanisms regarding social hierarchy that are mutually beneficial for domestication (it's key to remember that for dogs and cats especially it's thought that domestication with us occurred in both directions). The ability to form close social bonds with kin, and importantly with non-kin is vital for the sort of co-operative relationship that humans have with dogs.
It may be possible to breed sociality into unsocial creatures (there's evidence that cats have significantly increased their tolerance for close proximity with other cats after domestication), but doing so would require either significantly more time and effort than starting with a social creature, and/or advanced knowledge of animal husbandry. It may well be that our ancient ancestors had that knowledge, but it is unlikely that they had the surplus resources to engage in multi-generational projects without immediate (or even lifetime) benefits.
So, we're stuck with the felines that are already social. The earliest evidence of the domestication process starting with wolves is 27,000 years ago (earliest evidence of domesticated dogs is 14,200 years ago). So we'll look at the social feliforms that lived alongside humans at that point in time.
Panthera leo (African lions) are social cats that lived alongside humans in Africa, the eastern Mediterranean and the Middle East, and the Indian subcontinent. They are currently the only extant social cat (although very happy to be proved wrong about that!).
Panthera spelaea (cave lions) were also extant at this point, and lived alongside humans in northern Eurasia. Evidence suggests that cave lions were solitary, but there is limited evidence that some populations were social.
Machairodontinae such as Smilodon and Homotherium are likely to have been social. Smilodon definitely fits into the time period. The latest finds of Homotherium are 28,000 years old, but there is a possibility that they survived for another 1000 years and we just don't have finds dating to then.
These are all the known social true felines I know of.
Expanding it to feliforms, which would still be extant if all the dogs were wiped out, we get a few others.
Crocuta crocuta (spotted hyenas), and Hyaena brunnea (brown hyenas) are certainly social to at least the same level of wolves. Other hyenas like the striped hyena and the aardwolf do also display some social behaviours, but are less social than wolves. Still might qualify though. The cave hyena was also extant in eurasia during this time period, and was social.
The only other social feliform I can find is meerkats, who are very social indeed.
The next gateway to domestication for predators is size. It is a very, very unwise decision for early humans to attempt to tame, let alone move towards domesticating predators that can easily overpower them.
Wolves at the time domestication is expected to have begun weighed an average of 41-44kg depending on which species it actually was that became domesticated. If we take that to be a good target as it's significantly less than the average weight of a human at the time. We can reasonably include some flex as it's not a known thing, but something that weighs significantly more than a human is probably not going to happen.
Furthermore, we know from real-life examples of domesticated animals that breeding something to be significantly bigger than their ancestral body size comes with a significant number of health issues (see shire horses and percherons, and great danes and rotweilers). So, we don't want something that's too small either. It's almost certainly possible to breed large versions without the health problems, but this will take time. Remember, paleolithic people had much fewer opportunities to engage in long-term projects without immediate reward.
So, here's some averages for the above species:
- Lions: 120-250kg
- Cave lions: 200-350kg
- Smilodon fatalis: 160-280kg
- Smilodon populator: 220-400kg
- Homotherium: 190kg
- Spotted hyenas: 40-69kg
- Brown hyenas: 40-44kg
- Striped hyenas: 22-55kg
- Aardwolves: 7-10kg (up to 15kg)
- Cave hyenas: 102kg
- Meerkats: 0.5-2.5kg
So, we can probably discount all except spotted hyenas, brown hyenas and striped hyenas already. However, there's one more hurdle that we need to jump through.
One of the primary benefits that wolves and dogs offered to early peoples is as hunting companions. Humans are persistence predators. Wolves are also persistence predators. Humans are evolved to tackle big game, as are wolves. We're both highly specialised for endurance and tackling animals larger than ourselves.
Cats, by and large, are not persistence predators. Lions, tigers, jaguars, sabre-tooth cats, cheetahs, domestic cats...all hunt by ambush. As such, they are a poor match for our evolved hunting tactics. We'd blow their cover, and they wouldn't be able to keep up with us over the sorts of distances we travel. This would not necessarily be insurmountable to a determined selective breeding programme, but you're going to have to undo a significant amount of evolutionary adaptation (up to and including skeletal structure). This is way beyond the scope of early domestication.
Hyenas, however, are persistence predators. This is one of the reasons for their dog-like morphology via convergent evolution. Certainly spotted hyenas also hunt big game.
Meerkats also range over large areas relative to their size. However, they subsist entirely on animals smaller than themselves and as such are not adapted to big game hunting. Not so useful to early humans. This is also true of aardwolves.
Hyenas are the only feliforms extant during the time period since domestication began that are capable, let alone likely, of filling the same niche as wolves/dogs.