There's a bunch of phonetical differences:

  rus. Volk ~ ukr. Vovk
  rus. Aleksey ~ ukr. Oleksiy

Different suffixes:

   rus. Tarasov ~ ukr. Tarasenko, Tarasiuk

Ukrainian surnames often have no suffixes at all (more often than in Russia):

  rus. Melnikov vs. ukr. Melnyk
  rus. Kovalev vs. ukr. Koval

Although it doesn't say anything about a person's nationality for certain because of migrations.