Colored coins is one of my #1 favorite topics! The same issue (high fees) that plagued ETH would soon arise if doing "Colored Coins" for NFTs on BTC. Regardless, this could certainly be done. Colored coins was actually one of the 1st concepts that seriously drew my interest to this space.
One might think Lightning Network would be a good solution, but LN is fungible, so that wouldn't work.
Still, colored coins is an awesome concept and I'm planning to help with at least 1 use-case (fingers crossed!) in the next few months.
Theoretically possible but practically impossible, and one of the reasons that NFTs and DeFi will probably never be adopted on Bitcoin L1 unless the protocol changes.
[0] https://en.bitcoin.it/wiki/Script
[1] https://en.bitcoin.it/wiki/Fungibility
[2] https://sethforprivacy.com/posts/fungibility-graveyard/
[3] https://en.wikipedia.org/wiki/Colored_Coins
[4] https://www.youtube.com/watch?v=889JSfIaPzs