Написанно много, в детали вдаваться не буду но постараюсь ответить просто и ясно:

Любые изменения в договоре обязывают согласие всех без исключения лиц указанных в договоре и арендодателя. Съехал, ни съехал в отношении договора это значения не имеет. По этому:

Действительно ли может выйти один человек после написания Kündigung из договора и оставить 2х в нем? Без согласия этих 2х? Могут ли выйти 2 и оставить 1го?

Да, может, если все остальные и фермитер с этом согласны будут

Но теперь моя сожительница заявляет, что если после того как откажу 3м ее претендентам, и после 3х месяцев положенного установленного крайнего срока - ее выпустят из договора. Так ли это?

Однозначно: нет

- могут ли выходить квартиросъемщики из договора аренды по своей инициативе и с согласия арендодателя, но без согласия со-съемщиков?

нет

- действительно ли я должна согласиться на кого-то их 3х предоставленных желающих?

нет

- стоит ли мне обратиться к адвокату, и быть готовой, что они перестанут платить свою часть, после заявленных сроков? И если перестанут, какие последствия меня ожидают?

да, стоит. Фермитеру по барабану с кого бабло трясти, с кого найдёт с того и стрясёт.

- если родители будут платить, за своего ребенка, какие документы нужно от них?

никаких

- нужно ли мне бить тревогу и самой искать кого-то?

ну это уже Вам решать. Может у Вас доход такой, что всю квартиру сами содержать сможете и больше не хотите иметь сожителей, Вам решать. Вопрос только, согласиться ли на это фермитер?