But most of Europe seems to have shrugged at the Golden Horde being Muslim as far as any frenzy for coalitions.
No, they didn't. They basically saw them as the remnants of the dreaded Mongol hordes which, thankfully, had retreated east and weren't pushing west anymore. Compare that to the Ottomans, who were winning every war they fought and looked like an unstoppable tide for a while. One was past its prime and confined to its location, the other was new and didn't show any signs of slowing its expansion.
But how who owns central Ukraine is a major strategic concern to the Byzantines, assuming they're not otherwise hostile to the empire (and Poland-Lithuania seems to had interests away from Constantinople's)?
For Russia, it's the southern frontier.
For Byzantium, it's the area just beyond the northern frontier (Crimea).
The Byzantines fought every sect of Christianity they bordered and allied with most of them at different times, but they never seem to have had any particularly "we're both Orthodox" uniting their interests
That line only works in situations where the Catholic-Orthodox split is present. Pre-1054, it doesn't exist.
It also doesn't exist on the eastern border, where there are no Catholics.
Where the Byzantines
did have relations with the Catholic world, it varied between Teeth-Clenched Teamwork (ie. Crusades 1-3) and bitter rivalry (ie. the 4th Crusade and onward, relations with Hungary). They only cooperated with the Catholics for the 1st Crusade in the first place because they knew they couldn't push back the Seljuks alone, and their expectation was that the Crusaders would give
them the Holy Land instead of taking it for themselves.
By the time of the Great Schism, the Byzantines' weakness also meant that they didn't present the same kind of coalition-forming threat as the Ottomans (expansionist, seemingly unstoppable, heading westward). If they recover their strength and decide to do
Belisarius 2: Electric Boogaloo in Italy and the Balkans, they'll present the same kind of threat as the Ottomans did IOTL.
I can't think of any time "we share a religion" automatically meant alliance, especially between powers that simply don't share many common goals.
In the era of religious wars (ie. the 15th-17th centuries) that was pretty much a given, with few exceptions.
But interdenominationally speaking, there was Henry VIII's alliance with Charles V in the 1540s, despite the former having broken with Rome the previous decade and offending the latter with his treatment of Catherine of Aragon.
An alliance which didn't last long. As soon as France stopped being England's main problem, the alliance dissipated.
But for 16th and 17th century Europe as a whole, where the Catholic-Protestant division was omnipresent, religion determined the vast majority of alliances.
Anglican England also allied with Catholic Portugal against Catholic Spain in the 1640s to end the Iberian Union.
They supported the Portuguese rebellion for the exact same reason that the French supported the Turks and Protestants: the Hapsburgs were a big enough threat that any qualms about religion had to be thrown out.
As for not cooperating, a shared faith didn't do much to smooth over Bulgarian-Serbia-Byzantine relations at any point.
When everyone's the same religion and the nearest Catholics are in Hungary and northern Italy, religion doesn't serve as a useful political division.
Also, anything pre-1054 doesn't count because Orthodox and Catholic don't exist as political distinctions.
A cursory glance through the Kievan Rus' history also notes several raids against the Byzantines over the 900s-1000s, possibly over the Byzantine outposts on the northern Black Sea coast, so it's not like the Kievan Rus was entirely peaceful with the Byzantines.
See above. Wrong era. In fact, this doesn't just predate the religious wars. It predates
the Orthodox-Catholic Schism.
There's also the question of if Pan-Slavism actually happens (well, nationalism emerging in a form we'd recognize given this level of divergence is questionable, but still not completely irrelevant, methinks) and how Orthodox powers would handle either a non-Slavic Orthodox power dominating Slavs (like Austria over the Italians) or two competing Orthodox Slavic powers competing to dominate the Slavic world. That's another potential flashpoint (along with Black Sea domination) that religion doesn't butterfly away.
That's there, but that's for the era of nationalist wars (ie. the 19th century).
France and Austria were both Catholic
I already mentioned this.
Netherlands and England both Protestant
The Anglo-Dutch Wars only started toward the tail-end of the European religious wars, and that rivalry took a back seat when the French became the bigger problem again.
Sweden and Denmark Protestant as well
That had to do with the Vasa overthrow of Danish rule in the 16th century.
They also didn't form a long-lasting alliance with the Catholic powers over this, despite fighting several wars with Sweden. Only in one (the Second Northern War) did they cooperate.