Пока их ситуация известна только Вам, обсуждать ее не имеет смысла.
В любом случае, при любой ситуации, к приобретению ребенком граждан Украины гражданства Украины немецкие власти не имеют никакого отношения. А требовать доказательства того, что ребенок не приобрел никакого другого гражданства, если он претендовал на приобретение немецкого, это их право.

В чем будет выражаться нарушение этого порядка? Какой предъявленный документ, из предусмотренных Перечнем, будет указывать на попытку совершения нарушения? Какая из статей межправительственного соглашения запрещает гражданам Украины пересекать украинско-российскую/российско-украинскую границы совместно со своими, не достигшими 16-летия, детьми-негражданами Украины?
Другое дело, что в перечень документов с украинской стороны внесен документ, не относящийся к документам подтверждающим гражданство Украины. Но это проблема сторон, заключивших соглашение, а не вина граждан Украины и их детей.