Как создать отдел тестирования?
Возьмите опытоного QA и он все вам расскажет, как надо делать.
>1) Огромное разнообразие вариантов построения продуктов из блоков конструктора - что работает у одного заказчика, может не сработать у другого по разным причинам. На какой конфигурации конструктора проводить тесты?
На наиболее часто встречающихся или приносящих основной доход.
>2) К конструктору нет четкой спецификации (и не будет в данный момент), лишь список задач в баг-трекере, а значит тестировщикам непонятно что тестировать. Можно попробовать писать тесты на новые задачи и постепенно они покроют все, потихоньку добавлять тесты на функционал, который не попадает в новые задачи. Сработает ли? 
Сработает, но у разработчиков будет большая просадка по времени - так как тестировщикам надо будет спрашивать у них много о системе.
>3) Превышение возможностей подразделения по поддержанию тестов в актуальном состоянии. Скорее надуманная проблема, но тем не менее, может ли получится так, что тестов станет слишком много и при выходе новой версии продукта тестировщики не будут успевать актуализировать тесты под изменившуюся платформу?
Это уже проблемы отдела тестирования и того как они будут решать задачу, но в целом такая проблема есть, но без конкретитки тут говорить нечего.
Я знаю системы где 10к тестов держит один человек, и системы где 100 тестов поддерживает отдел из 6-7 человек.
первая мысль которая пришла в голову: если проблемы на стыке компонентов возникают, может сперва над архитектурой поработать?
Тестирование ведь всего-лишь находит проявление ошибок. А желательно устранять причины приводящие к их возникновению. Иначе вы будете тратить все больше денег на то чтобы находить ошибки, релиз будет откладываться, клиенты будут недовольны задержками обновлений. 
Почитайте багтрекер на предмет, каковы причины найденых ошибок.  Как правило есть несколько корней зла. Вот на это и стоит обратить внимание. 
У нас например ModelView слой программы выдает минимум треть ошибок, мы делаем автоматизацию, это дорого,  а надо просто нахрен выкинуть тот инструмент которым мы делаем UI и перейти на что нибудь, что будет валидироваться у разработчика на компьютере а не завтра утром на сервере после полной сборки. Другое дело что на такой шаг начальство пойти не может, они в рабстве у вендора этого инструмента.  Т.е. миграция возможна но не вдруг.