You mentioned making heros immune to spells. The problem that I see with giving them any complete immunities is that many decks depend on either spells or creature or weapon abilites exclusively. These cards are extremely powerful, so there has to be a variety of counters. I'm just gonna make a list of anti-creature cards I can think of and how various defenses could protect heros from the most powerful while no negating the weaker ones.
Spells:
Without any protections the three biggest abusable threats to heros are fire bolt, ice bolt and drain life. The best spell counter outside of those is gravity pull. Plague, lightning and mutation might be usable counters that should not be discouraged. Rain of Fire should be close to negilible. Chaos seed I don't know enough about the possible effects to think about. Mutation I'm also not sure about.
Weapons:
Owl's Eye is the obvious. The problem with the card is that its offensive power is the same as Rain of Fire's, but it is reusable.
Labotmizer - Completely over powered against heros. This equates to an instant kill.
Eternity - I'm not quite sure about this one. Doesn't kill the hero, but still is pretty damn powerful if the player is paying 20 mana per turn compared to the opponent's 3.
Creatures:
Maxwell's Demon - This should never be able to kill a hero at all. Insta-kill effects stuck
Fallen Elf - Not really sure. I don't like instant kills, but it does have a randomization on it.
Virus - Should be an effective card
Otyugh - Devour should be effective. If an otyugh has gotten that big, the other player deserves to lose.
Chrysoara - +1 infect per turn is pretty powerful, but should definatly be a viable counter.
Toadfish - See Chrysoara
Mind Flayer - Ridiculously overpowered versus heros
Parasite - See Toadfish
Shields: (only listing ones that prevent abilities from being used, attack power penalties aren't the issue)
Procrastination
Ice Shield
Because of the number of balanced and overpowered counters in each category, I don't think making them completely immume to one type is a good idea.
The cards I am worried about are:
Fire Bolt
Ice Bolt
Drain Life
Mutation
Labotomizer
Eternity
Maxwell's Demon (easily handled by giving the majority of heros low attack power)
Fallen Elf
The Hero specific defenses I can think of are:
Immunities - I don't like blanket immunties, but specifically targeted ones might work
Damage Caps - Either total amount of damage per turn or number of times the creature can be targeted per turn (not 0)
The best thing I've come up with is only allowing Heros to be targeted by direct damage abilities and specific effects including freeze, infection, time bubble, gravity pull, and maybe reverse time (not too sure about it). On top of this a direct damage cap of somewhere between 8 and 12 damage per turn would be fairly effective. This assumes most heros have health in the 15-25 range. Status effects would circumvent this cap. This would mean that any hero would have at least one turn on the board unless the opponent could apply either gravity pull, or 5 infections + 10 direct damage.
What I'm really questioning is if it should be possible to buff heros or not. The immortal king would be come very fun to play with buff cards, but other heros might lend themselves to overpowered combinations.