In order for this to be possible, you ned a POD where St. Peter is martyred in Constantinople, instead of in Rome. The reason why Rome is the seat of the Catholic Church is because Peter was killed there and because Jesus declared Peter to be "the stone that the builders rejected."
Yes, though as far as I'm aware Jesus never said such a thing about Peter. The reference to the stone that the builders rejected, a direct quotation from Psalm 118, comes in Matthew 21 as part of a parable addressed to the chief priests and the Pharisees. It is to be honest fairly opaque as to who might be meant by the stone, but I see no indication that it was Peter, and as far as I know that is not a view generally held. The more relevant passage is Matthew 16:13-19. The last two verses:
18 And I say also unto thee, That thou art Peter, and upon this rock I will build my church; and the gates of hell shall not prevail against it.
19 And I will give unto thee the keys of the kingdom of heaven: and whatsoever thou shalt bind on earth shall be bound in heaven: and whatsoever thou shalt loose on earth shall be loosed in heaven.
This passage is crucial tp the claim of papal supremacy as opposed to primacy, so as you correctly say a papacy relocated to Byzantium would need to be still asserting a succession to St Peter. Who according to Church tradition was Bishop of Rome, so even if not located in Rome, which during the Avignon captivity the papacy was not, the Roman episcopate still needs to be claimed for the succession to St Peter. The site of his martyrdom is not really the key to it, the key is that he was supposedly martyred in Rome because he was there as its bishop.
He would of course have struggled to be bishop of Constantinople, seeing as it was not yet founded. So for the Ecumenical Patriarch to make the Petrine claims seems a difficult proposition. A relocated papacy, filling the Roman see
in absentia, is possible; it was far from unknown for people to hold several sees at once and hardly ever go near any of them, just raking in the revenues, but in Byzantium there would be the twin problems of co-existence with the Ecumenical Patriarch and, even more problematically, the Emperor.
As observed above, a large part of the reason for the runaway nature of the papacy is that there was hardly ever an Emperor in Rome to hold the Popes in check. There were periods when either the Eastern or later the Holy Roman Emperor had the papacy more or less under his thumb, but mostly this was not the case, the Emperor was elsewhere and the Pope did as he pleased. In Byzantium, in contrast, if the Patriarch didn't please the Emperor the latter was right there, and many Patriarchs were replaced with varying degrees of prejudice for disputing Imperial authority, or seeming to.
Another part was the unwise Donation of Pepin, which ensured that the papacy would forever be mired in temporal affairs whether individual Popes wanted it or not (usually they did). A POD where Pepin had more wisdom, or foresight at any rate, might have produced a medieval and renaissance papacy of a more spiritual character, with no need for a Reformation. Or not, but there certainly would have been a large difference in the character of the institution and it quite possibly never would have become as deplorably corrupt as it did.
But I digress. A papacy permanently relocated to Byzantium would have faced all kinds of difficulties and would have become unrecognisably different from the institution as it evolved. Might just as well abolish it and have done.