Tienes que utilizar la función preg_replace que solo reemplaza un carácter. Y esto lo tienes que hacer mientras haya x en tu cadena. Para ello te tienes que apoyar en la función strpos()
<?php
$lista = '12345xxxxx';
while (strpos($lista, 'x')) {
$lista = preg_replace('/x/', rand(0,9), $lista, 1);
}
echo $lista;
?>
Espero que te sirva.