We could introduce a way to commit a PQ public key as a companion for a sec256k public key, without revealing the latter. A (later) soft fork could enforce that each sec256k signature must be paired with a PQ signature if such a commitment is there.

Both the commitment as well the PQ signature could go into a newly introduced section of the blockchain (like the witness) and get discounted to be on par with sec256k signatures. This way the tx rate would not be negatively affected.