Правильно: замужем за Андреем Гагаузом.
Мужская фамилия Кайнелайнен склоняется, женская – нет. Правильно: замужем за Андреем Кайнелайненом.
Мужская фамилия Куц склоняется, женская – нет. Правильно: замужем за Юрием Куцем.
Орфографически верно: не замужем.
Мужская фамилия Борщ склоняется. Правильно: замужем за Антоном Борщем (если ударение на первом слоге) или за Антоном Борщом (если ударение на втором слоге). Место ударения определяет носитель фамилии.
Если начальная форма фамилии - Стецишен, то верно: замужем за Сергеем Стецишеном, женат на Виктории Стецишен.
Запятая перед деепричастным оборотом нужна: Катерина встретила свою настоящую любовь, будучи уже замужем. Заметим, что если бы деепричастный оборот начинался с частицы только, то запятую можно было бы не ставить: Катерина встретила свою настоящую любовь только будучи уже замужем. Сравним пример: Они встретились только будучи уже взрослыми («Справочник по русскому языку. Пунктуация» Д. Э. Розенталя, параграф 20.3). Но обратим внимание, что частица только не «запрещает» запятую.