I can see it happening two ways
1) Carthage
2) as I was just beaten to, the Exarchate of Africa.
Carthage, frankly, needed to dominate the Atlas Mountains rather than just the coast, or get a resounding victory in Sicily. If you have a PoD that has Carthage allied with Sicily for the medium term, whilst it dominates Africa and can then draw on it for manpower as well as a trade resource, then I think Carthage would be more prepared for any later war (plus, a reliable ally in Syracuse/Sicily is a boon). The less mercenary army certainly would help them, as they can still back those troops with mercenaries galore from their trade). I won't lie, sometimes I think Carthage was probably the better option to make the Western Med catch up with the East economically.
The Exarchate may be cheating, but if Phocas doesn't usurp the throne, then assuming the Empire is able to survive Khosrau without a Heraclian Usurpation (I say it wouldn't be needed), then I think even if Mohammed rises as per OTL, and invades Africa after pushing the Romans back, I think the Exarchate would be able to hold off any invasion across the desert, as it hasn't used its resources to usurp the Empire. Regardless of what happens in the East, the Exarchate is then in the better position, and can start to build the west on its own merits. If it can bring the Berbers into their armies, then a Romano-Berber Exarchate could probably invade Spain and get the ball rolling out West.