Да, в ДМС мне тоже сказали: "обязательно отдать на таможне. Вот Вам еще один экземпляр справки".

И ДМС требовали получения и предъявления им (ДМС) этой справки?

Можете провести эксперимент. Возьмите справку с собой, но не предъявляете её никому на границе сразу, а ждите пока её у Вас поросят, а у Вас её не попросят :)

по приезду в Германию спокойно живу дальше и мне ничего и нигде больше оформлять не нужно?

В консульстве Украины - ничего.

А для гражданства все же нужно встать на постоянный КУ.

Не нужно.

У них на сайте это выделено.

Увы, сайт не является нормативно-правовым актом. Можете поинтересоваться у консульства, каким действующим нормативно-правовым актом установлена необходимость пребывания на консульском учёте для выхода из гражданства Украины.

Но это я могу сделать в любое время, когда Я захочу, как я понимаю?

Да, если Вам не жалко 18 евро и нескольких часов для его оформления.

Ох, напугала же меня эта тетенька из ДМС.

Они в ДМС любят пугать, особенно в Вашем одесском, да. Таким образом они повышают своё чувство собственной важности.