Could you not use zk-STARK for a post-quantum signature scheme?
Your private key is a random symmetric encryption key, your public key is the hash of the encryption key.
To sign you run an algorithm to encrypt a hash of data-to-be-signed with your private key and hash your private key to obtain the public key.
The signature consists of the encrypted hash, and zk-STARK proof of the algorithm execution trace and output.
Even if the signature size would be greater than SPHINCS+, verification of signature should be much faster?