A substituição de string é fácil. Gerar números aleatórios é provavelmente possível, mas será horrível ler e virtualmente impossível de manter (basta dar uma olhada em alguns dos scripts de amostra sancionados oficialmente ).
Eu faria algo como
replacement="xxxxx$(printf "%05d" $RANDOM | cut -c 3-5)"
sed 's/MyRegularExpression/'"$replacement/"
Isso é uma bagunça feia de citações, mas é provavelmente melhor que escapar de todos os caracteres especiais no regex que seriam afetados usando aspas duplas para todo o corpo sed.
Atualizar, com base no seu comentário:
perl -pe 's{my_regex}{ sprintf "xxxxx%03d", int(1000*rand()) }ge' file
Exemplo:
$ cat sample.py
def f1(a,b,c):
x = a + b + c
return x
def f2(a,b):
x = a + b
return x
$ perl -pe 's{def|return}{ sprintf "%s%03d", uc($&), int(1000*rand()) }ge' sample.py
DEF905 f1(a,b,c):
x = a + b + c
RETURN771 x
DEF146 f2(a,b):
x = a + b
RETURN199 x