C-h a replace-regexp , select the function, and look at its help string.
The solution will end up looking something like:
M-x replace-regexp : \([0-9]+\):\(.*\) \,(+ 1 \#1):\2
But with (format-time-string) instead of my (+1 1 \#1); I don't know time formatting functions in emacs elisp off the top of my head, sorry.
(Or use query-replace-regexp if you want interactivity.)