Написание с прописной нарицательных существительных, используемых не в своем обычном значении, потерявших свое прямое значение, регламентировано для имен людей (Ричард Львиное Сердце) и составных географических названий (Кузнецкий Мост, Ясная Поляна). Написание Волшебная Печенька соответствовало бы правилу, если бы это сочетание было прозвищем или географическим названием, например: деревня Волшебная Печенька. 

Название сети магазинов орфографически правильно было бы писать «Волшебная печенька» (независимо от ассортимента их товаров), но при этом приходилось бы учитывать, в каком виде зарегистрировано название торговой марки, и сохранять это написание в официальных документах.

В этой ситуации мы рекомендуем Вам обратиться в Институт русского языка им. В. В. Виноградова РАН за справкой об идентичности имен. Телефон ИРЯ РАН: (495) 695-26-60.

Собственное имя лица или кличка животного выступает в роли обособленного приложения, если оно поясняет либо уточняет нарицательное существительное (перед таким приложением можно без изменения смысла вставить слова а именно, то есть, а зовут его): Дочь Дарьи Михайловны, Наталья Алексеевна, с первого взгляда могла не понравиться (Т.); Отец мой,  Клим Торсуев,  известный мыловар, был человек тяжёлого характера (М.Г.); У дверей, на солнышке, зажмурившись, лежала любимая борзая собака отца — Милка (Л.Т.); А братья Ани,  Петя и Андрюша,  гимназисты, дёргали его [отца] сзади за фрак… (Ч.); Четвёртый сын ещё совсем мальчик,  Вася (Пауст.).

Помета затрудн. может по-разному интерпретироваться лексикографами. В Грамматическом словаре А. А. Зализняка она является в большей степени описательной, нежели нормативной. В предисловии к словарю помета комментируется так: «носители литературного русского языка в тех случаях, когда им в речи требуется по смыслу данная форма, обычно испытывают затруднение и нередко предпочитают обойтись вообще без этой формы, заменив слово синонимом или перестроив синтаксическую конструкцию» (подробнее см. в электронной версии словаря; нужный фрагмент начинается со слов «Сложную проблему для грамматического словаря...»). Нормативная оценка форм, образование которых вызывает затруднения, будет разной, вопрос о нормативности для таких форму решается индивидуально.

Слова казалось бы и конечно относятся к группе вводных слов, выражающих «оценку говорящим степени достоверности сообщаемого — уверенность, предположение, возможность, неуверенность и т. д.» (формулировка из параграфа 25.1 справочника по пунктуации Д. Э. Розенталя). Оценка чего-либо — часть отношения к чему-либо, поэтому характеристика слов казалось бы и конечно как выражающих «отношение говорящего к высказыванию» не ошибочна. Вместе с тем она неточна, поскольку «отношение говорящего к высказыванию» может выражаться вводными словами, указывающими не только на достоверность сообщаемого, но и на эмоции (к сожалению), способ выражения мысли (иными словами) и т. д. 

Следует писать с большой буквы, так как это уважительное обращение к одному лицу.

См. в словарях:

КОМПЛЕМЕНТАРНЫЙ, -ая, -ое; -рен, -рна, -рно. Спец. 1. Дополнительный, дополняющий. К-ые связи, отношения. 2. Связанный с комплементом (2 зн.).

КОМПЛИМЕНТАРНЫЙ, -ая, -ое; -рен, -рна, -рно. Содержащий похвалу, восхваления; хвалебный. К. отзыв. К-ая оценка. К-ая критика (содержащая лишь хвалебные отзывы о произведениях искусства и литературы). Комплиментарность, -и; ж. К. критики.

КОМПЛЕМЕ́НТ, -а; м. [от лат. complēmentum дополнение, довершение]. 1. Хим., физиол. Белковое вещество, содержащееся в плазме крови, которое под воздействием антител уничтожает инородные клетки. 2. Лог. Класс всех тех объектов, которые не являются членами данного класса. // То, что является дополнением к чему-л. Комплемента́рный (см.).

Очевидно, что в приведенных Вами контекстах речь идет о дополнительных услугах, то есть следует употреблять слова комплементарно, комплементарный.

Корректно: салат с вологодской уткой.