So when you have Prince Malchezaar in your deck with Baku, the hero power is upgraded, even if he triggers first and shuffles even-cost legendaries into your deck.
On the other hand, when you play Baku with the new C’thun (he starts the game as four odd-cost cards) the hero power doesn’t upgrade.
Is it intentional or just a bug? Odd-C’thun decks would be a lot of fun