Если Вы поменяете фамилию по российскому законодательству, то, разумеется, в российском паспорте Вам Вам фамилию поменяют. Но будет ли это основанием сменить потом фамилию по немецким законам в немецких документах, я не очень уверена.
В свое время, когда мы меняли фамилию, нам сказали, что мы можем почти бесплатно "онемечить" имеющуюся фамилию или за какие-то приличные деньги (около 500 евро на человека) поменять фамилию по желанию на любую немецкую, кроме очень сильно распространенных фамилий или фамилий известных людей. Может быть, имеет смысл сейчас написать письменное заявление на имя начальника Вашего ЗАГСа, чтобы получить письменный ответ с отказом и письменным же обоснованием? Может статься, письменно они и не станут отказывать... Почитайте NamÄndG, Erste Verordnung zur Durchführung des Gesetzes über die Änderung von Familiennamen und Vornamen и еще NamÄndVwV, может, найдете там какие-нибудь подходящие Вам параграфы.