Find and Replace will only work if the dates, times, date-times ar ordinary text. Generally they should be inserted as TextField objects. This also allows to easily find them for processing by user code. To work with dates inserted as ordinary text with the intention of changing the format, I would expect to be complicated beyond reason.
Anyway: Reconsider your idea of date formatting. Localization beyond the absolutely necessary is evil! Stubborn “national” formats are evil! Get rid of US dates, of course. They’re evil. However, don’t replace them with other evil formats, but stick basically to ISO 8601 which you may slightly modify or complete. Don’t “change the locale”, but “use good formats”.
Suggestions how to solve tasks of the kind (whether or not you accept my advice) you should find in the attached example. Tell me if there are errors, please.