I feel like I have to strenghten my point by saying that Pay2Win, does not mean that if you pay a certain amount of money you win every game against a person who did not pay. Pay2Win is, at least for me, an advantage that COULD (not will, but could) help you win against a player of the same skill level if you pay. And that's exactly what HearthStone is.
Back to my point with Arena in WoW. If you could buy all the gear by real money, it would be considered pay to win, even though you could get ALL THE ITEMS without paying the money and skilled players would still beat unskilled players who bought stuff for dollars, it is still pay to win as it's giving you an advantage over other players if you spend money.
And I feel I have to write this over and over again, but I'm not saying that is a bad thing, or an unusual thing or a thing that needs to be changed.