Ha JavaScriptben kellene írnom akkor callback-kel csinálnám:
s.replace(/%%.+?!%/g, match => match.replace(/@/g, ':'));
PHP-ben ez a preg_replace_callback.
Gyanítom rekurzióval meg lehet csinálni egy kifejezéssel is, kérdés, hogy megéri-e a komplexitást a viszonylag olvasható kódból a nehezen olvasható regex kifejezésbe átvinni.