If you require the $rhs to always be a Perl expression, then /ee works fine for me with these two examples. The $rhs in your example from the root node just needs to be adjusted to '"qqq"' so it's a valid Perl expression.

use warnings;
use strict;
use Test::More tests=>2;
{
    my $lhs = '\\{(.*?)\\}';
    my $rhs = '$1';
    my $str = '{abc}';
    $str =~ s{$lhs}{$rhs}ee;
    is $str, 'abc';
}
{
    my $lhs = 'xyz';
    my $rhs = '"qqq"';
    my $str = 'AxyzB';
    $str =~ s{$lhs}{$rhs}ee;
    is $str, 'AqqqB';
}
[download]

P.S. I see now that I should also be checking $@ inside the eval, to see if there were errors from the /ee.

Note Bug in eval in pre-5.14 - if I wanted to play it really safe, I might do use warnings FATAL => 'uninitialized'; just before the s///ee to make certain errors in the eval propagate.

(BTW, please use <code> tags to format your code)