Why not? If miners will be paid for burning coins, then I think they will have an incentive to do that. Some people thought about Proof of Burn, it is definitely possible to encourage miners to burn some coins, if they could be rewarded somehow for doing that. And burning coins in Proof of Burn should be done as garlonicon said, then it is clearly connected with mining, and no additional outputs are needed, so it requires no additional on-chain bytes.

I can also imagine that waiting 100 blocks may be inconvenient, so some miners could agree to mine a specific coinbase transaction on behalf of some user, just to receive some coins on-chain, that could be spent immediately. Also, because miners include transactions, it may be possible to do that atomically, like "I will give you those coins, only if you mine any coinbase transaction for me".