В соответствии с грамматическими нормами русского языка прозвище в таком синтаксическом случае выступает в роли приложения и не изменяется по падежам. В качестве примеров могут служить Владимир Красное Солнышко, Всеволод Большое Гнездо и Ричард Львиное Сердце.

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

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

Согласно орфографическим правилам корректно написание с прописной буквы только первого слова наименования: "Сердце столицы". 

Запятая не нужна.

Да, такая фамилия склоняется: Катеринки, Катеринке, Катеринку, Катеринкой, о Катеринке. 

Запятая обязательна.

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

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