А его дают?

А пока непонятно, и, похоже, решается прямо сейчас.

С одной стороны (§ 5 AufenthV):

(2) Als zumutbar im Sinne des Absatzes 1 gilt es insbesondere,
(...)
3. die Wehrpflicht, sofern deren Erfüllung nicht aus zwingenden Gründen unzumutbar ist, und andere zumutbare staatsbürgerliche Pflichten zu erfüllen
(...)
(3) Ein Reiseausweis für Ausländer wird in der Regel nicht ausgestellt, wenn der Herkunftsstaat die Ausstellung eines Passes oder Passersatzes aus Gründen verweigert, auf Grund derer auch nach deutschem Passrecht, insbesondere nach § 7 des Passgesetzes (...)

А § 7 des Passgesetzes гласит, что:

(1) Der Pass ist zu versagen, wenn bestimmte Tatsachen die Annahme begründen, dass der Passbewerber
(...)
7. als Wehrpflichtiger eines Geburtsjahrganges, dessen Erfassung begonnen hat, ohne die nach § 3 Absatz 2 des Wehrpflichtgesetzes erforderliche Genehmigung des Kreiswehrersatzamtes die Bundesrepublik Deutschland für länger als drei Monate verlassen will;
8. als Wehrpflichtiger ohne die nach § 48 Absatz 1 Nummer 5 Buchstabe b oder § 48 Absatz 2 des Wehrpflichtgesetzes erforderliche Genehmigung des Kreiswehrersatzamtes die Bundesrepublik Deutschland verlassen will;
9. als anerkannter Kriegsdienstverweigerer ohne die nach § 23 Absatz 4 des Zivildienstgesetzes erforderliche Genehmigung des Bundesamtes für den Zivildienst die Bundesrepublik Deutschland für länger als drei Monate verlassen will;

С другой стороны, смешно и грешно, но формально - на уровне законов и постановлений - ограничение выезда и консульских услуг не всегда и не совсем связано с воинским долгом. Например, запрет выезда мужчинам 18-60 лет вообще устанавливается не законом и даже не постановлением правительства, а ведомственной инструкцией Госпогранслужбы (которую еще попробуй найти в открытом доступе), которая просто запрещает оформлять их на выезд и предписывает отказывать в пересечении границы. А большинство нежелающих ехать в Украину уклоняется формально не от призыва в армию, а от обновления учетных данных. Плюс соответствующие параграфы Wehrpflichtgesetz в мирное в Германии время с 2011 года не действуют. То есть амты и суды в Германии - и других странах ЕС в том числе - могут занять любую позицию в спектре в зависимости от политических предпочтений и важности украинцев для экономики: от "отказывать и выдворять" (от выдворения до марта теоретически защищен 24-й параграф, впрочем) до "объявить украинские нормативные акты дискриминационными и выдавать Passersätze всем обратившимся". По интернету ходят новости с мнениями на этот счет, но посмотрим на практику.