жаловаться на что именно?
если сомневаетесь, то жалуйтесь и туда и туда.
хотя я пока не вижу формального повода для жалоб.

так вроде не вас подозревают, а ту контору ("gegenüber dieser Institution der Verdacht geäußert wurde") которая вам документ об образовании выдала (подтвердила?). Поэтому и подозрение что и вам (за взятку ? ) могли ненастоящий диплом (подтверждение) выдать.
что там за "Institution " имеется в виду? Заведено ли действительно на них дело в полиции?

«dieser Institution»-медицинский факультет университета, выдавший документ.
Речь идет о фразах: «Zwischenzeitlich hat das Polizeirevier ..... mitgeteilt» и «Herr .... nahm gegenüber dem Polizeirevier .... dazu bereits Stellung»,
которые не соответствует действительности, но ,основывакась на них, чиновница отказывает в разрешении на работу.

Запросто может оказаться, что этот запрос в полицию до полиции еще не дополз.
Попробуй вытребовать из чиновницы исходящий номер и прочую требуху этого ее запроса.
Всем.
Это классика бюрократии - затянуть волныку. В полиции, или как там правильно назвать, неспешно передадут бумаги в "криминальную лабораторию", которая будет мурыжить с ответом - потому, что есть более важные дела. Потом выдаст ответ - в огороде бузина, а в Киеве дядька.

Можно у местного шефа. Но шеф ответит, что "будет защищать своего работника всеми доступными правовыми методами" (с) Знаем-с, плавали.
Поэтому лучше подавать в полицию, при условии, что у вас есть все доказательства. И параллельно посылать всем жалобу на её действия.
Один бывший форумчанин образно говорил, что "бить надо дважды: один раз по голове, другой раз по крышке гроба" (с), однако моя практика показывает, что бить надо сразу "по крышке гроба" (с). Когда начинаешь с ними по-хорошему, то они хорошего отношения не понимают. И даже "битьё по голове" (с) не понимают, продолжают гнать дурку.
Поэтому надо сразу же пресекать все глупости с их стороны.

Вас пригласят на "собеседование".

Они работают, не торопясь.

Напишите Dienstaufsichtsbeschwerde на имя Behördenleitung.

Она в полицию не обращалась, она написала ,что получила сообщение из полиции о том, что там рассматриваются мои документы как фальшивые, поэтому разрешение на работу она не выдаст. В полиции заявили, что ничего подобного там не происходит.