I'm surprised I don't see more companions in Storm or other non creature decks, honestly. The nightmare lord or lurrus would prolly fit.
if kaheera didn't cost G/W G/W, maybe.
decks that can cast it probably have monastery mentor in them, and thus can't play it as a companion.
there aren't many that are really freely available in vintage aside from kaheera in truly creatureless decks, and the fact that any deck could be 80 cards if you really wanted to play yorion. odd/even/3cmc+ all are significant constraints. Jegantha means that among other things, you can't play force of will or force of negation. zirda (activated abilities) or umori(all spells of the same type) are free or close to it in the right deck, though they add constraints to the 75 (boarding in leylines or dismember with umori or cage/defense grid with zirda turn off the companion). lurrus's constraint are substantial: no narset, any other non w6 walker, tinker (unless it's just for vault/key), mentor. in legacy, it meant no gurmag, borrower, TNN, oko. these constraints were just worth it, because of what lurrus did, but wouldn't have been worth it for just a vanilla creature, which is what Kaheera effectively is.