Как мне доказать, что мой дед с нынешней фамилией является тем же человеком?

      Заключение о внесении исправления или изменения в запись акта гражданского состояния составляется органом записи актов гражданского состояния в случае, если в записи акта гражданского состояния указаны неправильные или неполные сведения, а также допущены орфографические ошибки (ст. 70, Федеральный закон от 15 ноября 1997 г. N 143-ФЗ «Об актах гражданского состояния»)
Решения о внесении исправлений и изменений в записи актов гражданского состояния принимаются, например консульским учреждением Российской Федерации за пределами территории Российской Федерации, если они были составлены на территории Российской Федерации.
Молдавская Республика образована после распада Советского Союза, но не признана ни одним государством.
 
В Вашем случае Вам необходимо руководствоваться Законом об актах гражданского состояния республики Молдова.
 Органы записи актов гражданского состояния действуют во всех городах — центрах районов и обеспечивают изменение, исправление, дополнение, аннулирование записей актов гражданского состояния или внесенных в них отметок;
Заявление об изменении, исправлении или дополнении записи акта гражданского состояния подается обладателем записи акта гражданского состояния или иным лицом, имеющим на это право, в орган записи актов гражданского состояния, в территориальном округе которого проживает заявитель.
   При отсутствии спора между заинтересованными лицами орган записи актов гражданского состояния рассматривает заявление об изменении, исправлении или дополнении записи акта гражданского состояния, если:  a) в записи обнаружены неточности, отсутствуют некоторые сведения, не все графы заполнены, допущены сокращения или орфографические ошибки (ст. 66 Закона об актах гражданского состояния республики Молдова)
 

Здравствуйте, Вам необходимо обратиться в суд с заявлением об установлении юридического факта.