Оба паспорта делает ДМСУ https://dmsu.gov.ua/, сначала внутренний, потом заграничный. Есть также сеть сервисных центров Документ-сервис https://pasport.org.ua/, где делают то же самое, но дороже (лучше сервис и обстановка).
1. Для внутреннего паспорта нужен старый паспорт, идентификационный код и свидетельство о браке (переведенное на украинский, перевод долже быть заверен нотариально). Конечно, свидетельство о браке должно быть предварительно апостилировано в Германии. Важно проконтролировать написание фамилии латиницей, оно должно совпадать с написанием в свидетельстве о браке. Небольшая трудность в том, что их программа делает транслитерацию согласно закондательству, а она часто не совпадает с немецким написанием фамилии. На этой странице сайта ДМСУ https://dmsu.gov.ua/poslugi/pasport-gromadyanina-ukrajni/id-oformlennya-pasporta-gromadyanina-ukrajni-u-formi-kartki-u-razi-obminu-pasporta-zamist-vtrachenogo-abo-vikradenogo.html в разделе Транслитерация указано, что можно требовать написание фамилии, отличное от транслитерации, если на то есть основание (а свидетельство о браке как раз таковым и является).
На каком этапе находится изготовление паспорта, надо отслеживать на том же сайте ДМСУ, если готов - идти и получать.

2. На основании нового паспорта в налоговой инспекции оформляется идентификационный код на новую фамилию. Документы - паспорт, старый код плюс могут попросить копию перевода свидетельства о браке.

3. После получения внутреннего паспорта и идентификационного кода - подаются документы на заграничный паспорт. Готовность также отслеживается на сайте ДМСУ.
В ноябре 2018 все заняло 2,5 недели (по срочным тарифам).