Почему с Widerspruch?

Потому что внесение данных о лице в Melderegister - это Verwaltungsakt.

Внесение данных в мельдерегистр это что, уже сам по себе Verwaltungsakt?

Думаю, что да.

Судя по всему, должно хватить простого:
"Согласно 12 статье закона РФ о гражданстве, перевод которой вы имеете ( в ваших методичках 🙂) , наш случай относится к варианту в): один родитель с гражданством РФ, другой - иностранец.В этом случае российское гражданство по рождению ребенок приобретает лишь в случае рождерия на территории РФ или в случае, если иначе станет лицом без гражданства".

А если переписка затянется, не приведёт в итоге к желаемому результату, а сроки официального обжалования уже пройдут?

И мельдеамт обязан von Amts wegen убедиться в неправильности данных и изменить на правильные

А что ему при этом запрещает воспользоваться § 25 BMG и требовать от лица подачи соответствующих заявлений? "Von Amts wegen" означает лишь, что мельдеамту следует изучить вопрос, а не бездействовать, но это отнюдь не означает, что этот анализ он обязан проводить исключительно самостоятельно.