Sorry for the slow reply, I’ve been traveling. Examples of using gettext filter are near the bottom of the doc page in the user notes.
You would need to substitute in the strings actually used for your situation. Previously I linked to the code where I believe the original “untranslated” English strings are defined. The first of several being:
'%s is your new username'
Instead of targeting the original English, you could instead target the modified text, the “translation” even though it’s still English. Since it’s in several parts and you don’t know where they separate, you’d need to dump out all strings passing through the filter and find the ones you need to target and alter. To limit the amount of data to sift through, you could add the filter from another action hook that fires close to when the message is output.