First, the good news: Full support for both capabilities and covenants can be added without changing the UTXO model whatsoever by adding some more programmatic capabilities to the language and doing some programmatic tricks. Since scriptpubkeys/scriptsigs continue to run ephemerally at validation time full turing completeness is much less dangerous than people fear. The main thing missing from what's expressed in transactions themselves is a coherent notion of a single parent of each output instead of the all-inputs-lead-to-all-outputs approach of transactions currently. It would also probably be a good idea to add in a bunch of special purpose opcodes for making coherent statements about transactions since in Bitcoin they're a very complex and hard to parse format.

Now for the controversial stuff. Once you start implementing complex general purpose functionality it tends to get very expensive very fast and is likely impractical unless there's a way to compress or at least de-duplicate snippets of code which are repeated on chain. Currently Bitcoin has a strong policy that deciding which transactions to let into a block for maximum fee is a strictly linear optimization problem and while it's possible to keep things mostly that way making it completely strict is unlikely to workable. About as close as you can get is to make it so that each block can reference code snippets in previous blocks for deduplication, so at least the optimization is linear for each block by itself.

Having covenants and capabilities at all is controversial in and of itself. With covenants the main issue is whether they're opt-in or opt-out. For a payment to someone to come with a rider where they could accept it and think their system was working properly for a while until you exercised some kind of retroactive veto on new action or even clawback would obviously be unacceptable behavior. But for payments to come with covenants but the recipient not even be able to parse them unless they're fully buying into that behavior is much more reasonable. 

The main issue which people have raised with capabilities is that if you were to have colored coins whose value was substantially greater than the chain they were tokenized on then that could potentially create a business model for attacking the underlying chain. While this is a real concern tokenized assets have been out for a while now and have never come close to causing this to happen, so maybe people aren't so worried about it now.

Given all the above caveats it turns out one weird trick is all you need to support general purpose capabilities: for a UTXO to have a capability its scriptpubkey asserts that its parent must either be the originator of that capability or also conform to the same parent-asserting format. More complex functionality such as supporting on-chain verifiable colored coins can also be done but it follows the same pattern: Capabilities are implemented as backwards pointing covenants.

If you'd like to see a fleshed out implementation of these ideas (albeit in a slightly different model) there's quite a bit of stuff on chialisp.com