These threads are always fun.
Can see North Africa being considered culturally part of an ATL Europe with surviving African Romance, Punic and Amazigh languages though likely embroiled in conflicts between various Christian or semi-Christian sects (perhaps even the odd fledgling non/anti-Christian gnostic belief system or two), while Zoroastrianism might be able to reform via a new post-Sassanid dynasty with Aramaic potentially remaining prominent in Levant, Mesopotamia as well as parts of Central Asia and Arabia.
"Europe" would strike me as a meaningless geographical construct in this scenario--far more likely is a divide between the Meditterranean and Northern Europe. As for North Africa, it seems like African Romance was associated with city dwellers and the Roman state apparatus (including Christianity and the Church), Punic was associated with indigenous landowners and peasants as well as heretical religions, and Berber unsettled tribal peoples and migrants so bound to be marginalised as in OTL. Whether its African Romance or Punic doing the marginalisation seems the end result of how religion evolves there.
Aramaic will be dominant in the entire Fertile Crescent, as it was since the the Persian Empire until Islam, though mainly as a language of peasants and the church.
The reason why Islam proved to be such a strong influence is that it is an internally consistent system of belief. So, even when it was brand new, it fit like a glove. This is why in the vacuum of Islam, we are likely to see another large, theologically consistent belief system in time take its replace, the main candidate being Nestorian Christianity.
Manicheeism was only a belief system of the elite, and Zoroastrianism and other isms were small and regional. At this time Nestorianism already spread from Egypt to India and China. THey had a Pope in Baghdad. Simple inertia would bring the Arabs under conversion just as the Nordics, Poles, and Russians all converted under a brand of Christianity over the next six centuries. But that's the thing...it might take another 600 years for these peoples to convert.
So, the Arabs, until their conversions, might simply be the Middle Eastern analogue of the Vikings. Without a coherent ideology to fight behind they won't be as successful (they'll be lucky to make it to Spain), but they will definitely go far, sack a lot of cities, intermarry with the locals like the Germanic tribes.
THe result is that Nestorianism today is a major world religion, probably bigger than Catholicism. The two versus one natures of Christ will be this battleground that everyone, even if they don't care, will know about by default. Nestorians would be considered non-Chrsitians (including Copts and Ethiopian Orthodox) and they likewise would see western CHristians as other.
THere is a good chance there is no modern analogue of SHi'ism, as Nestorianism was a very centralized religion. All religious texts and liturgies were in Syriac, even in India, and they had a Patriarch in which had unquestioned authority over the whole (something Islam did not have, thereby leading to factionalism.) So, the modern analogues of ISIS and what not will likely be fighting over the supposed differences of interpretations (modernists versus reactionaries) or, they may just fight over good old fashioned money and land without any religion factoring into it. Terrorism is mostly butterflied away, as Jihad is not the vehicle to attain forgiveness for personal sinfulness...the priest and the sacraments suffice for this. The butterflies of this alone in the 21st century are absolutely huge. I imagine that modern day warfare between the west and the middle east would have less of a humanitarian veneer and will simply be overtly imperialistic.
Nestorianism could easily schism, especially with how widespread the church was and how many national and ethnic borders it crossed. The church actually
did schism, several times, OTL. But the best example might be something along the lines of Avvakum, Old Believers, etc. in Russia. And a schismatic movement could easily embrace terrorism to a certain degree--look at the story of the death of Samson in the Bible, which a modern person reason could construe as a suicide bombing.
Of course, who's to say it isn't the Middle East ruling the west, with a Persian Empire as great as the Achaemenids dominating the place or something? Who knows what this world would look like by the 21st century.
North Africa likely will still be Donatist today, as DOnatism prevailed after the fall of Rome and for a time after the Arab invasion. ITTL, the Arabs that invade likely convert to Donatism. DOnatism henceforth will be seen as a scourge poised to invade Spain and Italy between the 8th to 15th centuries. We would all today have more familiarity with the importance of the personal holiness of priests and the sacraments, simply because Donatism will be considered an unchristian religion like Arianism and Gnosticism is today.
As for the Protestant reformation, it likely still happens. Being that Rome is not the undisputed biggest CHristian denomination, Protestants will find that they deal with more CHristological squabbles and they will have a less clear mantle of history to claim inheritance from. Protestants, often wrongly, claim that the ancient Church was being restored in the Reformation. In a world where four large ancient Christian groups still exist in force (Nestorianism, DOnatism, Eastern Orthodoxy, and Roman Catholicism) this claim is going to make even less sense.
Donatism barely existed in the 7th or 8th century, the Vandals basically killed it off when they persecuted non-Arians and the Exarchate church seems to have mostly healed the schism. That said, the North African church always had an issue with heretics, and it wouldn't surprise me in the slightest if a new and highly successful heresiarch popped up in the absence of Islam. It'll probably have a proto-nationalist characteristic to it like Donatism, and likely associated with the Punic-speaking populace--though that seems to have slipped into gradual decline during and after the Vandals, and the late 1st millennium is probably the last time for it to remain a major language. But the state-sponsered religion will be Catholicism, since Carthage and the Maghreb were under the Pope in Rome according to the Pentarchy.
Butterflies, man. If the Catholic Church shapes up, there won't be a need for a Protestant Reformation, though there could always be sects like the Waldensians, Hussites, Lollards, etc. Considering Protestant thoughts on Eastern Orthodoxy, I doubt that'll really be an issue.
Also, don't forget about the Syriac Orthodox Church, the other major Syriac Church. It's non-Chalcedonian but otherwise not associated with the Nestorian Church of the East. It was and is pretty major force in Syrian Christianity, and if the Arabs must convert to Christianity, just as likely IMO as the Nestorians. Especially since I believe it was strongest in the western part of the Aramaic-speaking world, closest to the Hejaz.
They would also participate in wars to the north and tip balances in major wars. I could also see the expansion of Arabs from Yemen into Africa as opposed to the Mid East, leading to possibly Arab states along Somalia and Ethiopia, in which case, Arabs could become a majority in Somalia, Eritrea, Adal, etc... And a large minority in Ethioia/Aksum. This would fit the likely trajectory of Arab civilization without Islam, a continued move to gaining slave populations and serving as unruly mercenaries for kingdoms to the North.
Why didn't the Arabs do that OTL in Somalia or Eritrea? The region certainly has a very "Arab" quality to it, but Somalia is pretty renowned as one of the most ethnically homogenous countries in Sub-Saharan Africa.
Without the Islamic conquest of North Africa, the region probably would have stayed much closer culturally and politically to Europe. Genetically too, maybe, depending on how much the Arab invasion changed the genetics of the population. Also, without a Reconquista, Portugal and Spain probably wouldn't become centralized as early as they did and so likely wouldn't discover and colonize the Americas, at least no as much as they did OTL. I wonder who would replace them.
Possibly one of the local Spanish kingdoms, probably on the west coast of Iberia? A Mauretanian kingdom is a cool possibility, since they'd be trading by both land and sea with Sub-Saharan Africa so would probably find Brazil one way or another.
I've read North Africa is pretty genetically mixed, like some people look very "Arab", others look like they wouldn't be out of place in Ancient Carthage or Ancient Egypt. I've sadly never been there to confirm.
Wasn't the reason that Colombus's voyages of discovery got financed was because the constant warfare, infighting & backstabbing in the Eastern Med & the Middle East made the spice trade with India unreliable.
Likewise the other Western European voyagers who set off West.
So if the trade routes to India aren't disrupted then no drive to finance searches for an alternative route thus the discovery of the America's happens in a totally different way.
Considering the Middle East is the crossroads of the world, it's highly likely at some point the spice trade will be disrupted, probably by nomadic steppe invaders or severe internal conflict in Persia.