You are correct that the meaning in your example sentences wouldn't change if you left out the word "over". From an informational/geographical perspective, "over" doesn't contribute anything.
But from a communication perspective it serves at least 2 purposes:
1) It makes the sentence slightly informal and a little bit friendly or intimate. "Over on Campbellton Road" is not an expression you would find in "Google directions", where you would more likely see an exact numerical address, e.g. "412 East Campbellton Rd." When you say "over", it has a slang-y undemanding vagueness that can put others at ease.
2) It also communicates that the speaker knows the area. You can hear that in his mind he is viewing his personal image of the area, and mentally "pointing" to a particular place by calling it "over there". He is inviting his listener to share in perceiving this imaginary mental map.