Mate, do the following :
a) set your region and language to Germany and German
b) go to settings, voice, and check that German is downloaded. Beware, it could show "German", but click on it and make sure it's downloaded (if not, it will be mentioned)
c) enable location and cortana
I'm not sure you want Cortana to speak English or German, but I think that if you region is set to Germany, Cortana can only speak German.
My father had not the French voice downloaded on his (FR) 630, which prevented Cortana from working.
If this doesn't work, yes, hard reset may be the solution. It won't erase your SD card, but you won't able to recover your apps: you'll have to reinstall them. But music/photos/etc will be preserved.