Насчет России не скажу, потому что я не имею российского гражданства.
Скажу только, что при регистрации брака в Дании фамилию Вам не поменяют, для этого нужно будет обращаться в посольства и ЗАГС Вашей/ее страны.

У меня получилось так, что американцы, например, признают датский СОБ без никиого апостиля, как есть, и визу и все остальное вклеили без проблем, а вот латышсткое посольство требует апостиля на СОБ не страше (!) одного года, плюс - перевод (СОБ на 4 языках. но латышского среди них нет!). Здесь в Германии мне СОБ тоже признавали в штандесамт, но только их свидетельство (подтверждение) о браке мое посольство мало интересовало.. Все зависит от внутренних правил приема документов в посольствах, это обычно указано у них на сайте.
Фамилию можно менять когда угодно, вне зависимости от "срока" замужества. Не могу себе представить, какие проблемы могут быть с Ауслендерамтом по этому поводу. Объясните, что там у нее квартира и все остальное на ее девичью фамилию - и все дела. Думаю, АБХ имя не столько интересует, сколько соблюдение правил пребывания/выезда/въезда в страну... Хотя - могу ошибаться. Знающие - пусть поправят.

Апостиль выдается датским министерством внутр. дел (если я не ошибаюсь его название по русски) и является действительным для всех стран Хаагенер конвенции). Для этого СОБ нужно отослать туда для протсавления апостиля. У меня ссылка на домашнем компе, если интересует могу выслать вечером в личку.