Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair?
Chaum-Pedersen protocol tweaked with Sigma AND composition should do.
The high level intuition: using Chaum-Pedersen protocol for DH-triple, one can prove knowledge of secret witness $\alpha$ in the following relation in (honest verifier) zero-knowledge:
$$
\mathcal{R}:=\left\{((x, y, z), \alpha)\in\mathbb{G}^3\times\mathbb{Z}_q: \quad y=g^\alpha \land z=x^\alpha\right\}
$$
where $(x,y,z)$ is the statement (&quot;claiming that they are a DH-triple&quot;)
Recall the following ElGamal encryption scheme:

Now let $y$ be your public key and $\alpha$ your secret exponent (secret key), let $x$ be the first part of the ElGamal ciphertext above (namely $v$ in the screenshot), and naturally $z = y^\alpha = g^{\alpha\cdot\beta}$ is the shared secret and let it be the $w$ in the ElGamal encryption process.
With Chaum-Pedersen Sigmal protocol above, we can prove knowledge of a secret key that produce a ciphertext for a certain message.
Finally composing two Sigmal protocols, one for each (message, ciphertext) tuple, using AND-proof construction, the verifier could easily verify that the two ciphertexts are encrypted under the same key as the two statements shared the same $y$. $\blacksquare$