My first instinct would be that the Byzantines would probably be operating very differently - both a prerequisite and a consequence of your scenario. Venice proved that trade domination can and did bring huge economic power - my first instinct would be to say that the Byzantines need to prioritise control and a garrison of at least Venice, so much so that I'd suggest that Venice, regardless of how it governs itself, is effectively made the Exarchate of Italy & Dalmatia - or something equivalent to that. Keeping Venice on side has one big advantage of fewer feuds between Constantinople and Venice as IOTL - but I can see the two coming to disagreements anyway, as Venice still has all its historic advantages, and so leans towards being the heart of a navy. In this case it is the navy of the Exarchate. If Venice is loyal, then we have a potentially powerful navy that can boost Roman authority, and a city that could be a perfect staging post for any invasion of the Po Valley - whilst at the same time flourishing and enforcing the economic domination of the Romans in the eastern Med.
You'd likely see Venice become the hub of Byzantine Trade into central Europe for sure, with the rest in Constantinople.
But really, the best PoD I can see for this, is the acceptance of powerful naval Exarchates. This would mean going all the way back to Belisarius and Justinian - and it only needs to be a minor PoD - the Balearic Islands are made the capital of the Exarchate of Spain, with its immediate responsibility to take control of the W.Med and establish Roman authority by sea.
Whilst it probably makes little difference (I mean, unless someone can see some powerful butterflies for a navy), other than retaining Roman Naval power in the West, and establishing a precedent for Naval Power over Land Power.