Proving that you have $k$ keys out of $n$ without revealing which keys they are I'm looking for a cryptographic algorithm where Alice can prove that she has at least $k$ private keys out of $n$ to Bob, without revealing which keys she knows.
As I wrote in a comment, I believe your solution only works with some public-key schemes, because usually a full-blown public encryption scheme must include randomness to allow encryption of low entropy plaintexts without others being able to guess and encrypt. (Still, it would probably allow verification of key-ownership in some such schemes if access to the underlying primitive like unpadded RSA is assumed.)

A patched solution is for Bob to use Shamir Secret Sharing to share a symmetric key, which he uses to encrypt all the necessary information to reproduce the public-key ciphertexts. That is, he creates a symmetric key, computes the shares and encrypts them using each public key. He then encrypts both all the coordinates and the steps taken to encrypt them, including any randomness the schemes may use, using the symmetric key.

(He does not need to reveal any coordinates in plaintext, but should encrypt all the public keys if Alice does not know them. This means the scheme reveals to Alice which the other public keys were if she has the $k$-subset.)

Alice will be able to verify that the coordinates are on the same polynomial and that they were indeed encrypted using each public key.