Российское консульство не занимается изменением имени и фамилии, эти данные должны быть изменены во внутреннем российском паспорте и консульство не имеет таких полномочий.

Это нужно делать в России, через ЗАГС, причём и фамилию и имя можно выбрать любые, не обязательно связанные с родственниками.

После получения нового паспорта РФ, необходимо получить новый СНИЛС, ИНН и загранпаспорт на соответствующее имя и уже с новым загранпаспортом в Германии получить новый Aufenthaltstiteln и внести изменения во все немецкие документы.

По информации на сайте посольства РФ в ФРГ (линк), вариант 2: ...в соответствии с Законом Российской Федерации «Об актах гражданского состояния» российское консульское учреждение в Германии предоставляет государственную услугу по государственной регистрации перемены имени (фамилии, имени, отказе от отчества) гражданам России, достигшим 14-ти летнего возраста, постоянно проживающим в ФРГ и состоящим на консульском учете. Заявление о перемене имени принимается от заявителя при его личном обращении в консульский отдел.
Подробнее здесь.
В конце оказания услуги выдаётся свидетельство о перемене имени.

Из этого я делаю вывод, что воспользоваться услугой смены имени, фамилии и отчества через консульство можно. Например, генконсульство РФ в Бонне предосталвяет список необходимых документов на сайте (под заголовком "Необходимые документы", линк). Для человека с незарегистрированным на территории РФ браком или не состоящим в браке, а также не имеющем детей, для смены имени, фамилии и отчества достаточно следующих документов: Заявление (форма 20), заграничный паспорт, свидетельство о рождении.

По поводу замены внутреннего паспорта, СНИЛС, ОМС, военного билета, диплома об общем (среднем) образовании, диплома о высшем образовании - сомневаюсь, что консульство этим занимается. Предполагаю, что как и в случае с просроченным внутренним паспортом, эти документы (кроме дипломов) нужно заменить в отведённый срок в случае посещения РФ. Если находишься за рубежом, то эти документы остаются действительными, просто нужно вместе с ними предъявлять свидетельство о смене имени. Дипломы заменить можно, но не обязательно.

Документы, заменой которых наверняка занимается консульство: Заграничный паспорт, свидетельство о рождении. Эти документы наиболее важны для жизни за рубежом.