The OP wrote that Deutsch Post (probably) or Posten (possibly) messed it up.
The Germans messing it up seems much more likely. There are plenty of Norwegian addresses containing Å/Æ/Ø.
Yeah but that does not make any sense. Deutsche Post would not have changed the label so the address would still be correct.
So whatever the German post thinks the address is, the label should have been scanned within Denmark, and the issue is likely that the Denmark post’s contractor is incompetent, rather than “lol Germans don’t do foreign names with funny letters” (which is not what the OP wrote, but is the vibe in a lot of replies).
And indeed, a post code should render this very difficult in the first place.