Two PoDs.
First - Constantinople should fall in 717. If the Arabs suceeed, the Balkans up to the Danube would be open to Muslim rule. Arabs vs Avars and Sclavenians sounds like an intresting prospect , methinks.
Second PoD: The Ummayads mounted multiple large scale raids - and full scale invasions of Gaul in the early 8th century. The Battle of Tours was just the best known one. If the Franks were in a state of civil-war , along with the Lombards simultaneously , they're likely to go down the same way as the Visigoths . ESPECIALLY if Constantinople is under Muslim rule. Remember , Christanization was quite firmly grounded in Western Europe by 500 or so . There's no reason to think that a 717 conquest of Gaul would end up in a Islamic Western europe by 900 or so . We might see Islam proceeding in two directions - from Gaul , and from Bolgar / Muslim Rus .By 1400 , I doubt there'll be any Pagans left except in Northernmost Europe. I suspect , as per OTL , the Lithuanians would be the last major power to cling on to Paganism , before being Islamized.
There is also no reason to think that eventually , Andalusia might discover the Americas , or a Muslim analog to France or England .
Christanity would probably be a minority religion today , encompassing no more than 5 % of the population . That being said , it may be less divided.
What's more interesting however, is whether the Industrial revolution will take of as per OTL in an Islamic Europe. Given the abundance of Coal in North Western Europe , if the butterflies do not provoke a Song Dynasty Industrial age in China , I suspect Europe will still be the first to undergo an Industrial Revolution. Whether sooner or later , is highly debatable.