Maybe I'm ignorant about how bitcoin mining works but it seems like a miner could just compute the above hash for multiple public keys they own so as to guarantee one of them hashes out to the desired constraint (less than K, I believe??)
Indeed. You are right. This is why we proposed equation (2) and (3)
Once again, if a miner has multiple private keys they'll just compute the above hash for each one.
If i was a miner, that's what I would do. Unless it was computationally too expensive.
Indeed. But it reduces mining only between miners who can share their private keys with each other. Which means that there a large number of miners won't be able to create pools unless they trust each other 100%.