Unable to maintain formatting on find/replace

You can do away with Select and copy to.

    Range("C3").Select
Selection.Copy

and just use

Cells.Replace What:="dd/mm/yyyy", Replacement:=Format(Range("C3"), "dd/mm/yyyy"), LookAt:= _
xlPart, SearchOrder:=xlByRows, MatchCase:=True, SearchFormat:=False, _
ReplaceFormat:=False

Cells.Replace What:="xx/xx/xxxx", Replacement:=Format(Range("C5"), "dd/mm/yyyy"), LookAt:= _
xlPart, SearchOrder:=xlByRows, MatchCase:=True, SearchFormat:=False, _
ReplaceFormat:=False