Hedenstad debuteerde in 2006 voor Elverum Fotball, de club waar hij doorstroomde vanuit de jeugdopleiding. Op 7 juni 2008 debuteerde hij voor Stabæk Fotball in de Tippeligaen tegen Strømsgodset IF. In totaal speelde hij 94 wedstrijden in de Noorse hoogste divisie. Op 17 juli 2012 ondertekende hij een vierjarig contract bij het Duitse SC Freiburg. Op 1 september 2012 debuteerde hij in de Bundesliga tegen Bayer Leverkusen.