. Нужно ли мне менять фамилию прежде чем подавать документы ?

Я думаю, что в этом нет смысла. Вы всегда сможете доказать, что изменение фамилии деда (с Иванов на Шульц, предположим) произошло по решению суда. Т.е. с доказательством Вашего происхождения от деда Шульца проблем быть не должно. А вот с доказательством того, что Ваш дед Иванов (Шульц по решению суда) сын своего отца-немца Шульца, могут возникнуть проблемы, здесь BVA, наверняка, засомневается в происхождении.

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

Если дед был репрессирован не по национальному признаку, а это, весьма, вероятно:

его отец репрессирован в 1937г

то справка ничем особо не поможет.

А если еще:

и сведений о нем больше не было, его мать умерла в 1935г (болезнь)

то получается, что Вам просто не от кого вести происхождение. VBA требует наличие живого предка с немецкой декларацией на 1945-й год или хотя бы на 1941-й.

Я пребывал в Австралии ( 1 год учился - повышал квалификацию и 1 год работал потом по контракту) – может ли это осложнить дело?

Только обучение могло бы не сыграть роли, а работа потом по контракту - очень может быть.