Такие образования разговорны.

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

В настоящее время различия в значениях оборотов со словом кроме не сказываются на пунктуации: и в том и в другом случае предусмотрено выделение запятыми. Однако в прошлом обороты со значением включения знаками препинания не выделялись. Ср.: Кроме учителей на собрание пришли и ученики. — Кроме учителей, на собрание никто не пришел».

В соответствии с рекомендацией справочника в Вашем случае обособление нужно. 

Правило об отсутствии запятой между сочинительным и подчинительным союзом при наличии в главном предложении второй части подчинительного союза – лишь частный случай более общего правила: запятая между союзами не ставится, если придаточное предложение невозможно изъять или переставить в другое место. Если в главном предложении есть вторая часть подчинительного союза, то изъятие или перестановка придаточного невозможна. 

Попробуем переместить придаточную часть в Вашем предложении: И разговаривали с ним, а он отвечал, если хотел, или молчал, а он говорил с ними, как с равными себе, [когда пришли старейшие племени]. Такая перестановка невозможна, поэтому запятая между союзами а и когда не нужна.

Словосочетания решить проблему, решение проблемы корректны, они зафиксированы словарями русского языка.

Такие конструкции корректны.

Названия кафедр и факультетов пишутся со строчной буквы, а названия институтов — с прописной.

Выбор варианта зависит от контекста и от того, каким является замысел автора.