It seems FME Server needs unicode in the request - to for instance fmedatadownload, and if sending utf-8 it fails.
For instance *fmedatadownlad/myrepository/myworkspace.fmw?myparameter=Bærre lækkert
But this will work:
fmedatadownlad/myrepository/myworkspace.fmw?myparameter=B%C3%A6rre%20l%C3%A6kkert