Na gespeeld te hebben voor nationale selecties tot 17, tot 19, tot 20 en tot 21 jaar debuteerde Kahlenberg in april 2003 onder bondscoach Morten Olsen in het Deens voetbalelftal. Sindsdien speelde hij meer dan dertig interlands. Kahlenberg kwalificeerde zich met het Deense nationale team voor het WK 2010. Bondscoach Olsen nam hem daar ook als een van zijn 23-selectiespelers mee naartoe en liet hem als basisspeler aan het toernooi beginnen.
Kahlenberg nam met Denemarken –21 deel aan de EK-eindronde 2006 in Portugal, waar de ploeg van bondscoach Flemming Serritslev werd uitgeschakeld in de eerste ronde. Kahlenberg scoorde drie keer in evenzoveel groepswedstrijden dat toernooi.
Kahlenberg nam met Denemarken ook deel aan het EK 2012 in Polen en Oekraïne, waar de selectie van bondscoach Morten Olsen in de groepsfase werd uitgeschakeld. Op de 1-0-overwinning op Nederland volgden nederlagen tegen Portugal (2-3) en Duitsland (1-2), waardoor de Denen als derde eindigden in groep B.