Странно - что на временном, как это получилось? Я так понимаю, что речь идет о параграфе, где детям дается немецкое гражданство, если родители-иностранцы прожили определенное время в Германии? По-идее, у вас обоих уже должен быть ПКУ, а значит - и у детей тоже.
Остальное katran76 уже осветил, пока я писал :-)

Просто следует различать:
- пограничника на выезде должнп интересовать законность выезда, плюс, наверное, законность пребывания в его стране, и не больше.
- пограничника на въезде интересует законность въезда.
- таки да, при регистрации на самолет можно показать соответствующий документ, чтобы развеять страхи работника авиакомпании. Если спросит, конечно.
Одним словом, манипуляций с паспортами не избежать.
Впрочем, если АБХ поставит в Ваш паспорт ..эрлаубнисы для детей, то можно ограничиться только им. Или наоборот - показывать только немецкие документы детей, правда, я не в курсе что будет спрашивать немецкий пограничник при выезде. Хотя, наверное, в документах детей есть данные о родителях.