Он 73 года рождения и у него нет никаких таких справок

Справки о реабилитации выдавали лицам, которые подвергались репрессиям по нац. признаку и были рождены до 1956 года. Ваш отец сюда не входит.

Однако есть огромное НО, в этой актовой записи у моего деда указана фамилия его мамы (она там тоже указана в строке родителей), а во всех последующих документах фамилия отца деда (у меня тоже такая фамилия). Никаких справок об изменении фамилии конечно же нет

БВА сомневаются в родстве. Обязательно нужна справка о причине смены фамилии последующих документах деда. Если смена в последующих доках фамилии связана в связи с бракосочетанием родителей, то родство прослеживается.

Подойдет ли такая справка или стоит делать запрос на СОР деда?

Я думаю, такая справка, скан которой Вы выложили, не подойдет.

Родители деда были расписаны?

Еще вопрос: СОР деда у меня нет. Это вообще в Казахстан надо ехать, но никто не поедет, надо запрашивать, как это делается?

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

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