Hallo yogi84,
schau mal unter welchen Umständen dir die Erlangung eines Passes zumutbar ist:
§5
AufenthV Allg. Voraussetzungen der Ausstellung des Reiseausweises für Ausländer
1) Einem Ausländer, der nachweislich keinen Pass oder Passersatz besitzt und ihn nicht auf zumutbare Weise erlangen kann, kann nach Maßgabe der nachfolgenden Bestimmungen ein Reiseausweis für Ausländer ausgestellt werden.
(2) Als zumutbar im Sinne des Absatzes 1 gilt es insbesondere,
1. derart rechtzeitig vor Ablauf der Gültigkeit eines Passes oder Passersatzes bei den zuständigen Behörden im In- und Ausland die erforderlichen Anträge für die Neuerteilung oder Verlängerung zu stellen, dass mit der Neuerteilung oder Verlängerung innerhalb der Gültigkeitsdauer des bisherigen Passes oder Passersatzes gerechnet werden kann,
2. in der den Bestimmungen des deutschen Passrechts, insbesondere den §§ 6 und 15 des Passgesetzes in der jeweils geltenden Fassung, entsprechenden Weise an der Ausstellung oder Verlängerung mitzuwirken und die Behandlung eines Antrages durch die Behörden des Herkunftsstaates nach dem Recht des Herkunftsstaates zu dulden, sofern dies nicht zu einer unzumutbaren Härte führt,
3. die Wehrpflicht, sofern deren Erfüllung nicht aus zwingenden Gründen unzumutbar ist, und andere zumutbare staatsbürgerliche Pflichten zu erfüllen oder
4. für die behördlichen Maßnahmen die vom Herkunftsstaat allgemein festgelegten Gebühren zu zahlen.
Um also eine Ordnungswidrigkeiten-/Strafanzeige abzuwenden solltest du dich mit deinem Konsulat/Boschaft in Verbindung setzten und Dir einen Passersatz für die Aussreise ausstellen lassen, sofern "wie du bereits geschrieben hast" die Neuausstellung in Deutschland nicht möglich ist. Kläre für dich die einfachste Verfahrensweise zur Ausstellung, vielleicht ist es ja möglich, dass du nur zur Abholung nach Mazedonien reisen musst.
Gruß
Beppo