Документы надо приводить в соответствие, тем более что российское гражданство у вас сохранилось. Поэтому на основании свидетельства о перемене имени меняете российские паспорта (и загран, и внутренний), потом можно в России регистрировать брак. С признанием его в Германии проблем нет никаких - делаете апостиль на свидетельство о браке и переводите на немецкий, заверяете перевод у нотариуса.

У моего мужа тоже два гражданства, но регистрировать брак по его загранпаспорту нам отказались (в разных загсах, в двух городах узнавали). Поэтому мы зарегистрировали его (мужа) на сайте Госуслуги, на Госуслугах подали заявление на регистрацию брака, потом отдали паспорт на замену. Т.к. у него в России не было прописки, замена паспорта заняла 1 месяц. Регистрацию брака тоже надо ждать минимум месяц со дня подачи заявления. Т.к. у вас случай посложнее - имя не соответствует документам, может быть не получится параллельно все сделать - тогда регистрация брака возможна после получения новых документов.