Using the \A anchor will make the regex fail as soon as it recurses since it will try to match the beginning of the string (hence only the first example string succeeding in your case). If you're matching nested parens then Regexp::Common::balanced can help you out e.g

use Regexp::Common;

my @examples = qw/
  (*********)
  (***(*)***)
  ((***))
  (((***)))
  ((**)**(**))
  (((())))
/;

for( @examples ) {
    chomp;
    print "$_: ";
    print $& if $_ =~ $RE{balanced}{-parens=>'()'};
    print "\n";
}

__output__

(*********): (*********)
(***(*)***): (***(*)***)
((***)): ((***))
(((***))): (((***)))
((**)**(**)): ((**)**(**))
(((()))): (((())))
[download]