Если справку я получу, как долго милиция будет снимать с учёта?

Если речь идет о выходе из российского гражданства и связанных с этим действиях, то снятие с учета (выписка) в России обычно делается ДО получения справки об отсутствии долгов по налогам. И даже если сделать наоборот (это не запрещено), выписка вообще никак не связана с получением справки об отсутствии долгов по налогам.

Только с ней могут снять с регистрации в РФ.

Кто Вам такое рассказал? Это не так! С регистрационного учета в России снимают безо всяхих справок об отсутствии налоговых долгов, проверено на совесть, в том числе лично. Иногда люди выписываются перед отъездом за границу и только через много лет, выходя из российского гражданства, получают налоговую справку.

Про то, как получать налоговую справку, на форуме подробно писали уже много раз, посмотрите в архивах форума. Вот, например, мой собственный старый пост именно на эту тему: https://foren.germany.ru/showmessage.pl?Number=34844261&Bo...

Подскажите, пожалуйста, всю процедуру выхода из гражданства через консульство.
...
Сразу оговорюсь, речь идёт о Дании, не Германии..

Если речь идет о Дании, то и информацию надо смотреть на странице соответствующего российского консульства в Дании, а не на немецком форуме. Даже в Германии от консульства к консульству есть различия, так что в российском консульстве в Дании тоже запросто могут быть свои особенности, о которых немецкий форум не знает.