I'm not sure how to get the timestamp back into the appropriate string in the proper place(s). I have tried using a subroutine with search and replace, i.e.s/<regex to find date>/&<subroutine to calculate date's timestamp>/ge, but I continue to get syntax errors (I assume because you can't call subroutines inside a regex).

You don't have the subroutine inside the regex, and you don't have to. Your approach is sound. So the syntax error must be in the details. Which you did't post.