2) насколько критично, что нет СОРа деда?
3) как ещё можно доказать родственную связь деда и его родителей?

Возможно, Вас заинтересует эта тема: https://foren.germany.ru/aussiedler/f/34832246.html?Cat=&page=2.85&view=&sb=&part=1&vc=1

4) насколько критично, что мой СОР повторный (слышал, что лучше оригинал отправить, пусть и без декларации). Если критично, то возможно получить его или его копию из ЗАГСа (ЗАГС отказался мне его выдавать, ссылаясь на то, что в нем уже не актуальные данные)?

Если взяли справку об изменениях, что вносились в актовую запись, то должно ее хватить. Но если в ЗАГСе все еще хранится Ваше первичное СОР, то можно попробовать договориться, чтоб Вам его выдали буквально не несколько часов для снятия и заверения копии у нотариуса, потом вернете. Первичное СОР будет убедительней любых справок.

5) Где мой дед мог получить паспорт? Точнее - когда репрессированным начали выдавать паспорта? Я так понимаю, что в 1944м ему вряд ли его выдали? Стоит ли пытаться искать место выдачи паспорта, чтоб получить выписку из ф1?

Спецпереселенцы стали получать паспорта после 10 марта 1955 года по месту спецпоселения. Ваш дед декларировал себя немцем? Можете выложить справку на него, чтоб понимать подвергался ли он лично репрессиям по нац. признаку и каким?

В 1944 вывезены немцами в Польшу в деревню Феликсов (название деревни не точное), где рыли окопы, затем были в Германии (это не точно) и в апреле 1945 репатриированы в Харьков, где дед работал на заводе №135 до ноября 1946 г. Затем переселен в Марийскую АССР с одним из братьев, затем в Казахстан в г.Тимиртау. Я был бы очень благодарен, если б вы мне подсказали, где почитать информацию о судьбе немцев с.Цебрикова (Гофнунгсталь), особенно интересен период ВОВ.

Сделайте запрос в Бундесархив на счет наличия у деда гражданства Германии, которое он мог получить во время пребывания там. Если этот факт подтвердится, то Вам не нужно будет искать его СОР, Вы сможете вести происхождение непосредственно от деда, как от гражданина Германии. Его возраст на июнь 1941-го уже не будет иметь значения. Также Вас, наверняка, заинтересует и другая информация, что может храниться в Бундесархиве о Ваших родных.

Можете предварительно поискать деда в этом открытом архиве http://www.odessa3.org/search.html если он там есть, то очень велика вероятность того, что гражданство он получил.

Более детальную информацию по гражданству времен войны и как сделать запрос в Бундесархив можно найти в этом разделе форума: https://groups.germany.ru/707262.html?Cat=