Корректно: заведующий отделением, заведующие отделениями.

Да, это деепричастие, на это указывает и суффикс, и вопрос, и синтаксическая роль слова в предложении.

Запятая не нужна, поскольку в подобных примерах сказуемое не имеет законченного смысла без сравнительного оборота.

В первом случае верно без пробела, во втором – с пробелом.

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

Словообразовательный разбор

Схема разбора:

1)    Поставить исследуемое слово в начальную форму.

2)    К исследуемому слову подобрать производящее.

3)    Объяснить значение производного слова через значение производящего слова (слов).

4)    Выделить производящую и производную основы.

5)    В производном слове выделить средство словообразования.

6)    Указать способ словообразования и процессы, сопутствующие словообразованию.

Разбор слова поверье:

1)    поверье — начальная форма существительного;

2)    поверье ← поверить;

3)    поверье: ‘предание, основанное на суеверных представлениях, приметах, необычных явлениях чего-либо, в которое кто-либо поверил’;

4)     повери- — производящая основа, повер[j] — производная основа.

5)    средство словообразования — суффикс -j-, который на письме передается с помощью разделительного мягкого знака: повер[j-е];

Такое же словообразовательное средство с тем же значением используется при образовании других отглагольных существительных, например: бесчести-ть → бесчест[j-е] (бесчестье).

6)    способ словообразования — суффиксальный, при словообразовании происходит усечение производящей глагольной основы: повери-. 

Если необходимо разобрать слово по составу (морфемный разбор), то словообразовательный разбор дополняют:

1)    анализом всех словоизменительных морфем слова.

2)    анализом всех словообразовательных морфем в слове.

Для слова поверье при морфемном анализе нужно выделить:

1)    окончание -е, которое является окончанием им. падежа (или винит. падежа, если в такой форме слово стояло в предложении; формы именит. и винит. падежей у этого слова совпадают), ед. числа, ср. рода.

2)    Словообразовательную приставку по-, с помощью которой образовалось слово поверить от слова верить (способ словообразования — приставочный). Это глагольная приставка, которая образует глаголы совершенного вида от глаголов несовершенного вида, ср.: бить → по-бить, мирить → по-мирить и др.

Полный разбор по составу: по-вер-j-е

1. Запятую нужно поставить.

2. "Вплоть" избыточно.

Словосочетание и составное глагольное сказуемое — это единицы разных классификаций. В первом случае мы определяем тип связи между словами, во втором — говорим о роли в предложении, которую может играть и словосочетание. Если словосочетанием считать соединение двух самостоятельных слов, связанных подчинительной синтаксической связью, составное сказуемое может быть выражено словосочетанием, образованным примыканием. От главного слова словосочетания мы можем задать вопрос к зависимому инфинитиву: хочу (что?) гулять, пообещал (что?) вернуться, начинаю (что?) петь. Точно так же мы задаем вопрос от главного слова к зависимому в случаях, когда инфинитив выполняет другую роль в предложении: попросил (о чем?) выйти.

Есть мнение, что составные сказуемые не являются словосочетаниями, потому что семантически главным является как раз инфинитивный компонент (см. ответ № 319367), но обычно подчинительную связь в словосочетании принято устанавливать по формальным, а не семантическим признакам. «Русская грамматика» в т. II, § 1775 «Примыкание инфинитива» в качестве субъектного примыкающего инфинитива приводит примеры хотеть остаться, намереваться уехать, начать говорить и т. д. Эти словосочетания представляют собой типичные составные глагольные сказуемые.