Such a war is unlikely to result from one side just deciding to go forth and slay, so the most likely (and still very unlikely) starting point would be escalation out of Italy. In that case, the most likely outcome is a points win for the Carolingians in theatre, followed by a Byzantine attrition victory. If Charles had put the resources he poured into the Saxon and Avar wars into taking out the Exarchate and Southern Italy, he probably could have managed. Byzantium has no allies to use for leverage in the area and naval power projection is of limited use. But of course, that would just be the start.
I can't see Charles managing to put together a global coalition (Harun ar-Rashid or the Barmaqids is a different story). The Bulgars are a good bet, but IMO about equally likely to turn against the Franks (especially if it happens after the object lesson of the Avar War). Byzantium, on the other hand, has the option of using the Andalusi and Maghrebin Arabs to catch the Franks in their flank. Probably not a good idea in the long-term view, but from Constantinople, an Arab Apulia might well look more attractive than a Frankish.
Charles' main problem is that his military machine is excellently suited to exactly one thing - producing land armies of highly motivated, self-supporting fighters for lucrative wars of conquest. His naval force depends on the few Lombard and Aquitanian cities he controls, he doesn't have garrison troops worth mentioning and he tends to lose conquered areas if he can't find local collaborators. Byzantium has naval power, cash flow and garrison forces, and they are hard to hurt where it matters (Anatolia, Thrace and Constantinople). As far as I can see, the only power than can beat them for good is the Abbasids. If Charles allies with the BUlgars and takes all of Thrace, what has he gained? Nothing that the Byzantines won't have back in another few decades.