The Azure Horn Shaman is all about positioning. So the best way to counter it is to have ways to change where it is standing before you destroy it.
Depending on what classes you play, there are some cards you could consider:
Lyonar
- Magnetize - “Pull Any Minion to the space in front of your general”
This will allow you to move the shaman away from the other minions, allowing you to kill it efficiently and prevent its dying wish buffs from occurring.
Songhai
- Juxtaposition - “Switch position between any two minions”
Same idea as with Lyonar, move the shaman away from his buddies, then attack it.
Abyssian
- Daemonic Lure - " Deal 1 damage to an enemy minon and teleport it to any space on the battlefield"
Also a positioning spell, which can adjust your enemy minions locations, to prevent the bonus health from being applied.
Vanar
- Mesmerize - “Teleport an enemy minion or General one space”
- Hearth-Sister - “Opening Gambit: Switch Positions with any other minion.”
Here we can slide the shaman out of range, and cleanly remove it.
Any Factions
- Repulsor Beast - “Opening Gambit: Push a nearby enemy minion to any space.”
- Ghost Lynx - “Opening Gambit: Teleport a nearby minion to a random space”
Ghost Lynx is more risky, but if you need a 2-cost minion instead of a 3 cost, it might be the better card for your deck, after looking at your curve.
And if all else fails, and the Azure Horn Shaman has already triggered before you draw any of your repositioning spells/minions, we can rely on the Trusty Lightbender. (Opening Gambit: Dispel ALL spaces around it.) By placing the Lightbender in the spot where the Azure Horn Shaman was located when it died, it will dispel all the +4 health buffs that were given out by the Shaman.
I hope these card ideas will help you modify your decks to counter the pesky Azure Horn Shaman.