И Вас с Новым годом!
ФИО меняются, если хотите, конечно, после получения Einbürgerungsurkunde и до получения постоянных Rersonalausweis и Reisepass. Делается это в ЗАГСе. Если ЗАГС в Вашем городе нормальный, то сделают сразу. Если ленивый, то могут и потянуть кота за хвост. Я буквально только что в другой ветке про это написала:
Поменять ФИО в разных землях занимает от 15 минут до 1,5 месяцев. (Зависит от того, насколько быстро хочет работать ЗАГС - мы с мужем в Хессене за полчаса всё поменяли, ребенок в BW такой же переменой месяц занимался, потому что там, во-первых, всё только по терминам, а во-вторых, зачем-то опять проверяли через все базы данных, причем очень неспешно, хотя это только что было сделано перед выдачей Einbürgrtungsurkunde; на время перемены ФИО там (в BW) сразу выдали временный аусвайс на старые ФИО, причем по изо-норме, с апострофами . В Хессене взяли по 20 евро с человека, в BW это было бесплатно.)
Rersonalausweis и Reisepass заказываются в Bürgerbüro/Bürgerdienste/Bürgeramt (ну или как называется эта организация в Вашем городе) после перемены ФИО.