Another approach

• Don't use recursive function.
• Iterate over the data structure.

_apply_($menu, qe/Some Item/i, sub {
    $_->{description} = 'I have been Changed!!';
}

sub _apply {
    my $menu = shift;
    my $descRE = shift;
    my $code_ref = shift;

    foreach my $entry (@$menu) {
        next if ref($entry) eq 'ARRAY';

        if (defined $entry->{menu}) {
            # recursive call
            _apply($entry->{menu}, $descRE, $code_ref);
        }

        $code_ref->($entry) if $entry->{desc} =~ $descRE;
    }
}