Я как раз не хотел бы, что бы у Вас сразу появилось отрицание в силу сложности поисков. Как показала моя практика при желании можно найти очень многое. На 60% зависит от упорства и на 40% от удачи.
У меня, например, довольно много информации о деде немце нашлось в Советских Архивах, во-видимому, потому что эти архивы Московские и хорошо сохранились. А вот с немецкой стороны архивной информации сохранилось очень мало, потому что дед из Кенигсберга и от архивов Восточной Пруссии остались рожки да ножки. Но даже в этой ситуации с помощью добрых людей на немецких генеалогических сайтах удалось найти официальные документы подтверждающие и адрес и гражданство деда и даже узнать в каком подразделении воевал, был ранен и попал во французский плен прадед в 1й мировой войне. А потом я сам используя сложные запросы в Гугл нашел объявление прабабушки от 1957 в газете переселенцев из Восточной Пруссии в память прадеда умершего в 1947 г. и, зацепившись за информацию, выяснил и историю семьи после 1941, когда разорвались связи и получил СОР и СОБ прабабушки. Правда за последние уже доплачивал за поиск немецкому генеалогу. Весь процесс занял 2 ГОДА. И шел он крайне неравномерно - то долго ничего, то прорыв.

Логика поиска должна быть такова - сначала местные архивы в Украине, что бы понять из какой части Германии приехал прадед и когда, получить о нем больше информации. А далее уже писать на немецкие генеалогические форумы типа https://forum.ahnenforschung.net для того получить консультацию где находятся реестры о рождениях и браке. Они могут быть где угодно и, скорее всего не в Бундесархиве. Например, в моем случае СОР жителей восточных территорий хранятся 110 лет в Standesamt 1 in Berlin, а затем переводятся в Landesarchive Berlin. Но у Вас точно не так. Нужно иметь минимальную информацию о корректном имени, дате и месте рождения и тогда с хорошей вероятностью Вы найдете документы прадеда в Германии.

А Бундесархив нужно копать, как Вам правильно здесь написали, для поиска возможного немецкого гражданства полученного в случае эвакуации семьи в Германию во время войны.