I think Bane of Doom will see lots of play now, doesn't even need to be in a demon deck.
I pulled Illidan in a different match with it.
On reddit someone figured that it averages out at pulling a ~4.4 mana minion now, prior to the change it was a ~2.8 mana minon.
So you spend 5 mana for a 4 mana minion after killing something. Pretty sweet tempo swing. And it can easily win you the game if it pulls a legendary.
There are like 3 really bad outcomes: Blood Imp, Voidwalker, Mistress of Pain
A couple poor but acceptable outcomes: Flame Imp, Void Terror
The rest are good to exceptional