Правильно: в городе Нью-Йорке, в штате Нью-Йорк. Топонимы обычно не склоняются в сочетании с родовым словом штат. А вот в сочетании с родовым словом город топоним склоняется, если он русского, славянского происхождения или представляет собой (как в рассматриваемом примере) давно заимствованное и освоенное наименование. Такие названия можно считать исключениями из процитированного Вами правила (статья дополнена этим примечанием).

В данном случае элемент -Парк не обозначает собственно парка. Ведь речь идет не о названии парка, а о названии гоночной трассы. Тогда как Уолл-стрит - это улица, Пятая авеню - это авеню, а Гайд-парк - это, действительно, парк. Ср.: Кузнецкий Мост (моста там нет).

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

Аньер-сюр-Сен, Аньер-сюр-Сена [сэ] (гор., Франция)

Витри-сюр-Сен [сэ], нескл. (гор., Франция)

Шалон-сюр-Сон, нескл. (гор., Франция)

Камаре-сюр-Мер [рэ, мэ], нескл. (гор., Франция)

Рошфор-сюр-Мер [мэ], нескл. (Рошфор) (гор., Франция)

Трувиль-сюр-Мер, Трувиль-сюр-Мера [мэ] (Трувиль) (гор., Франция)

Конде-сюр-Нуаро [дэ], нескл. (Конде) (гор., Франция)

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

См. в «Письмовнике».

Верно: (где) в Йошкар-Оле.

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

Аналогия с Йошкар-Олой: Коламбус-Сёркл (иноязычный родовой термин, входящий в географическое название, не употребляется в русском языке как нарицательное существительное).

Название города Йошкар-Ола склоняется, поэтому корректно: города Йошкар-Олы.

Если это первое слово в предложении, то правильно: Йошкар-олинский, если это первое слово официального названия, правильно: Йошкар-Олинский. Если это слово не является первым словом официального названия и стоит не в начале предложения, то верно: йошкар-олинский.

В полном академическом справочнике «Правила русской орфографии и пунктуации» приведено такое правило: в названиях учреждений, организаций, начинающихся географическими определениями с первыми компонентами Северо-, Южно-, Восточно-, Западно-, Центрально-, а также пишущимися через дефис прилагательными от географических названий, с прописной буквы пишутся, как и в собственно географических составных названиях, оба компонента первого сложного слова, напр.: Северо-Кавказская научная географическая станция, Западно-Сибирский металлургический комбинат, Санкт-Петербургский государственный университет, Орехово-Зуевский педагогический институт, Нью-Йоркский филармонический оркестр.

Поэтому правильно: Северо-Западный институт печати, Санкт-Петербургский экономический университет, станция метро «Юго-Западная».

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