Интересно, а можно ОДНОВОЕМЕННО через российский ЗАГС из Харькова запросить имея на руках :

Скорее всего, можно. Я заказывала одновременно СОС на прабабушку по маме и справку о том, что сведения о рождении дедушки (ее сына) не найдены из разных ЗАГСов, СОС пришло раньше, но мне его отдали только после того, как получили и справку на дедушку, т.е. после того, как подтвердилось родство (пусть даже и справкой об отсутствии сведений о рождении) при этом я еще и СОС на дедушку получила, в котором указано было место рождения и справка, соответственно, была из места его рождения, так что у сотрудницы ЗАГСа вопросов не возникло. И СОС на бабушку, дедушку и отца (их сына) я тоже заказывала одновременно с СОРом отца, имея на руках лишь свой СОР, все получила в своем ЗАГСе, опять же, одновременно. Т.е. при заказе документов никто не требует от Вас подтверждать родство, но при выдаче документов обязательно попросят доказательства.

СОБ бабушки и смену фамилии на фамилию мужа. Ну или справку об актовой записи о браке и смене фамилии (что можно спросить не знаю)

Запрашивайте "сведения о браке", а там уж что пришлют, мне прислали справку о браке, в ней тоже отражена смена фамилии.

А если запрашивать справку об угоне в РФ или Украине и приложить родство до бабушки, то можно и на прабабушку получить, указав, что она была не Штирлиц. как в СОР у бабушки, а Иванова на тот момент (правда без документального подтверждения), она 1902 года рождения (т. е. более 100 лет)?

Не знаю. Но зачем Вам эти справки? Если бабушка и прабабушка были натурализованы и сведения о них хранятся в немецких архивах, то Вам не надо доказывать репрессии, как подтверждение того, что они разделили судьбу немецкого народа. Я так думаю.