Proof-of-burn as usually described doesn't change bitcoin's validation rules, at all. I'm mostly aware of its usage in higher level protocols such as identity protocols which simply reference the burnt coins and maybe some data attached to them in the OP_RETURN output.
Proof-of-stake as originally described didn't require any protocol changes either. It is simply a mechanism for counting votes for or against a proposition (such as checkpointing a block) by weighting those votes according to the coins the pubkey signing the vote is protecting. This is a higher level protocol which can affect the client / wallet operation, but not the actual validation rules so no fork is required.
If you integrate proof-of-x in with mining, then yes hard forks are required. But why do that? It ends up weakening security instead of strengthening it.
Ahh, I see what you mean. I was originally exclusively talking about mining new blocks - essentially chasing the idea of a blockchain without a power-hungry mining backend.
Proof of burn probably translates to a 'cost' the best, so for identity extensions it makes sense (either that or use PoW). PoS or PoD probably are more suited to 'renting' type situations where you need to show intent for some period but want your funds to remain exclusively yours. (Or voting as you mention).
Instead of repurposing an opcode you could write a meta-network (like Mastercoin) that searches for commands after OP_RETURNs and if it finds a network identifier proceeds to interpret the trailing data by some other ruleset. Either way the argument stands.
Why? Because I want to see what happens. If it's insecure then an attack should be possible, but there are some conditions where an attack is much harder, so there are different properties to each form of currency, and neither is universally inferior to the other.