how do you effectively create a spam-protection mechanism? Filter and hope?
Proof of Work is a quite good filter. Today, you can pay only with fees. But it is possible to allow lower fees, if you provide more Proof of Work instead. And I guess there is some equilibrium somewhere, where users could accept paying N satoshis fee, with M difficulty. And then, you can decide, if you want to provide more coins, or more hashrate, to get your transaction confirmed.
Also, as long as OP_CHECKSIG, or its equivalent, is used almost everywhere, enforcing it is quite easy: the smaller your DER signature is, the more Proof of Work is needed to make it. Which also makes the whole transaction smaller, and can save you some satoshis on fees.
So, it is even possible now, to some extent. The main problem is that doesn't contribute to the whole network's chainwork. But well, if someone is against Merged Mining, then it can be used as it is: if you require a signature smaller than N bytes, then everyone, who will want to double-spend it, will need to re-mine it, by solving the same Proof of Work challenge from scratch.
Also, we can look at some numbers, to estimate, how many hashes are needed, if there is a lot of competition:
hash=00000000000000000000eaa0b9031bf81c368df29bb62a27794f7d7a38308f36
difficulty=1701f303
target=00000000000000000001f3030000000000000000000000000000000000000000
satoshis=314736509=0x12c27f7d
target*satoshis=000000000000249156c825770000000000000000000000000000000000000000
And then, some users will never meet 0x1701f303 difficulty. But more of them could meet 0x1a249156 difficulty instead, which could be a price for lowering your fee by one satoshi, if there will be many people, trying to do the same thing.
Which means, that if fees will be high, then it may be worth grinding your signatures, and making some satoshis out of it, by sending your transaction with the same fee rate, which could take less bytes.