I think you undersell Goblins, though I understand they aren’t the most “stereotypical” shaman.
In reality though, they simply took the traditional give/take relationship, formalised it through contracts, and used technology to help harness the power gained.
As for restoration specifically? Well, there is a lot of fighting that goes on in Azeroth, and I imagine magical healing can earn a pretty penny.
Remember, the elements are not benevolent beings, but chaotic entities. From the Shaman overview:
Shaman are spiritual guides and practitioners, not of the divine, but of the very elements. Unlike some other mystics, shaman commune with forces that are not strictly benevolent. The elements are chaotic, and left to their own devices, they rage against one another in unending primal fury. It is the call of the shaman to bring balance to this chaos. Acting as moderators among earth, fire, water, and air, shaman summon totems that focus the elements to support the shaman’s allies or punish those who threaten them.
Chaotic entities with wills of their own that can be bargained with and a chaotic race with a knack for striking deals for their own benefit? Fits like a glove to me.
I would argue that Vulpera resto shamans would be higher up, as would Pandas, probably. Vulpera resto shamans make sense to me. My Vulpera shaman’s RP is that she did water seeking and water keeping for the desert caravans.