In the KDE-settings I can set my language and formats to different locales. It lets me choose between a bunch of them. In this list also is the locale en_DE.UTF-8 (it's listed as en_DE though).
However as soon as I select this particular locale, I get into trouble. When I now run locale, I get the error
locale: Cannot set LC_ALL to default locale: No such file or directory
and the listed locales now do also show en_DE.UTF-8 for some fields.
Short version: After setting the locale in KDE's settings you have to manually double-check whether the set locale actually exists.
As it turns out KDE doesn't care what locales are actually installed on your system. It lets you use non-existing locales without any warning, which was exactly the case here. The locale en_DE.UTF-8 didn't exist. This can be checked by running locale -a and searching for that particular locale in its output.
Therefore I had to go back to the KDE settings and change all en_DE settings to proper de_DE that I saw where present earlier. As soon as this was done (and the changes took effect after a fresh login), the problems where gone.
These settings are located at /etc/locale.conf and ~/.config/plasma-localerc
