Another option to deal with the power level, if restriction doesn't work, is unrestriction of competitive options that do not work together with the companions, such as necropotence for Lurrus and Gush for the singleton companion (as examples, I don't want to start a b&r discussion here).
Power-creeping cards is honestly probably the best way to do this, but I think it would have to exist in this start the game with X space. I'm not sure specifically the ones you listed are correct to lure people away from the existing 10 beasts, but now that this design space is open you need to fill it with other things for the sake of variety. It would take a lot of convincing to tell me that you would not want a free card every game, so probably it's better that there are more free cards competing in that space to determine which one you want than to try to have a situations with haves and have nots.
Heres the thing, I do not believe that companion is broken as a mechanic, and as a result I do not believe there is justification for a rules change to it, because there are companions that exist right now that are a perfectly fine and restrictive enough not to matter. If the mechanic was truly broken then arguably you would find a way to include one no matter what. Looking at all formats in general, Lutri, Umori, Obosh, Jegantha, and Kaheera are either too restrictive or too low impact to matter on any sort of concerning level. That means that some of the cards are unbalanced, not the mechanic. Therefore I find it hard to justify a rules change.
Lurris, or really any of the companions, are not so good that it is going to convince dredge to run mana even if it could use them, and likewise it is not going to warp itself to do so. In other formats, something like Burn is not going to ruin how efficient it is just for +1 spell that isn't a burn card. Tribal decks like Merfolk or Goblin or elves are not going to screw up there decks so they can run an off tribe 5 mana 4/4 that has a useless ability. Even at that the utility you get in some lists that can run some of these without altering themselves at all is minimal in a lot of cases. Some versions of Legacy reanimator could conceivably run Jeganth, but why would they want to? Probably rather just have the sideboard slot.
If anything, I think one of the design mistakes with the companions is that Lurris cannot be run with copies of himself, but every other companion can be with the exception of Lutri who can only be run with 1 other copy. If we were running 3/1 then a restriction is much more prominent a penalty on the card, or maybe they should have been designed so that none of them could be played with themselves?
I'm curious to see what happens. I suspect that if they have more cards like this already planned for the future you will never see a ban and you just need to accept that Lurris is basically part of the power 10 now until some oof the other ones come out. You may see him banned in other formats where a ban matters but once again I fundamentally believe this card is functioning as they planned and they won't make their first power level ban in vintage over it.