В России используется вариант Алма-Ата, Алма-Атинская область, в Казахстане принят вариант Алматы, Алматинская область. См. также ответ на вопрос № 296089.
Верно с прописной.
Это существительное мужского рода, склоняется: Оредежа, Оредежу, Оредеж, Оредежем, об Оредеже.
С прописной: Московская область, Наро-Фоминский район.
В официальных названиях учреждений с большой буквы пишется первое слово и входящие в состав названия имена собственные, например: Агентство по физической культуре и спорту Ярославской области, Комитет по делам молодежи Московской области.
В сочетании г. Пермь Пермской области зависимые слова Пермской области, грамматически связанные с существительным Пермь, играют при нем роль несогласованного определения, называющего постоянный признак (см. параграф 53 «Полного академического справочника» под ред. В. В. Лопатина и приведенный в нем пример табуретки с золочеными ножками).
Во втором приведенном Вами случае сочетание Пермская область грамматически не связано со словом Пермь, оно несет в себе дополнительную информацию, а потому его уместно оформить как вставку в скобках: г. Пермь (Пермская область).
Да, элементы адреса разделяются запятыми.
Предпочтительно: на территории.
