while (1) {                                                           
    last                                                              
       unless $sentence =~ s!###RAND\{([^{}]+)\}!get_rand_arr_el($1)!e
+;
       print $sentence."\n";                                          
}
[download]

The  while (1) { last unless ... } loop is more concise and clear and IMHO better if written
    1 while $sentence =~ s!###RAND\{([^{}]+)\}!get_rand_arr_el($1)!eg;
Just replace the  1 with  print $sentence."\n" if the debug print is needed.

Also: Use of the  /g modifier with the  s/// substitution allows killing multiple birds (substitutions) with one stone (loop pass).

Update: Also: Lana: Be sure to test all this thoroughly. Otherwise, you may end up having even more trouble with the planets!