Вы обособили правильно (с помощью тире с двух сторон выделяется приложение с пояснительным значением).

Это сложноподчиненное предложение. Придаточные части когда возник вопрос и какой бренд использовать выделяются запятыми: Когда возник вопрос, какой бренд использовать, мы однозначно выбрали эту марку.

Полагаем, в заголовке можно отказаться и от кавычек, и от родового слова. И вот почему: кавычки выделяют собственные наименования из основного текста; будучи заголовком, слова "Омская марка" уже достаточно выделены.

Марочные названия вин пишутся в кавычках с прописной буквы. Без кавычек и со строчной буквы пишутся названия сортов вин: шардоне, мерло, рислинг. Скорее всего, в ресторанном меню употребляются именно марочные названия, а следовательно, необходимы кавычки и прописная буква.

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

Лучше так: Молодой художник Марк Миллер, один из лауреатов выставки, дал интервью журналу.

• Справочники рекомендуют писать названия марок автомобилей в кавычках с прописной буквы: автомобили «Волга», «Вольво», «Ниссан», «Шкода», а названия самих автомобилей как технических изделий – со строчной буквы в кавычках (кроме названий, совпадающих с собственными именами – личными и географическими). Например: «кадиллак», «москвич», «тойота», «ниссан»,  но: «Волга», «Ока» (совпадают с именами собственными, поэтому пишутся с большой буквы). Исключения: «жигули», «мерседес» (совпадают с именами собственными, но пишутся со строчной). Однако на практике различить, в каком случае наименование представляет собой название марки автомобиля, а в каком – наименование технического изделия, часто представляется затруднительным: Всем автомобилям он предпочитает «Тойоту» / «тойоту». В спорных случаях решение о написании с прописной или строчной буквы принимает автор текста.
• Названия, написанные латиницей, в кавычки не заключаются: автомобили Toyota Yaris, Peugeot 306, Daewoo Matiz, Škoda Fabia, Lada Priora.
• Неоднословные названия (марка и модель автомобиля), написанные кириллицей, пишутся через дефис, при этом все части наименования пишутся с прописной буквы: «Лада-Приора», «Тойота-Королла», «Рено-Меган», «Ниссан-Теана», «Хёндай-Гетц», «Ниссан-Альмера-Классик», «Сузуки-Гранд-Витара». Но: «Фольксваген-жук» (перекличка с нарицательным существительным).
• Аббревиатурные названия пишутся без кавычек: ЗИЛ, ВАЗ, КамАЗ.
• В бытовом употреблении названия средств передвижения пишутся без кавычек, например: Приехал на стареньком москвиче (на роскошном кадиллаке). Без кавычек пишутся также разговорные названия машин с уменьшительно-ласкательными суффиксами, напр.: москвичок, фордик, уазик.

Женское имя Макс, подобно таким именам, как Эдит, Кэтрин, Мариам, не склоняется, а значит, не может быть отнесено к какому-либо типу склонения. В дополнение см. 295319

Знаки препинания в примерах расставлены верно.

Условные названия заключаются в кавычки: галерея «Глобус», галерея  «Марс», галерея «100 своих». Но: галерея Уффици, галерея Тейт.