Use the evaluate switch:

use warnings;
use strict;

my $user_defined_string = "abcabcabc";
my $user_defined_search = '(a)';
[download]

my $user_defined_replace = '---$1---';
[download]

my $user_defined_replace = '"---".$1."---"';

print "before: $user_defined_string\n";
$user_defined_string =~ s/$user_defined_search/$user_defined_replace/e
+e;
print "after: $user_defined_string\n";
[download]

prints:

before: abcabcabc
after: ---a---bcabcabc
[download]

BTW: you are aware that your user can execute pretty much any code using this technique?. You may want to do some aggressive filtering on the expressions that are allowed, and that may be pretty tricky to do!