This is how I fixed it.

my $re;
$re = qr/
    \[ # Opening bracket
    ( # Capture the contents
        [^][]+ # Body of a link
        |
        (??{$re}) # Or recurse
    )+ # added per diotalevi's instructions
    \] # Closing bracket
    /x;

$k = "a[b[c[d]]";
$k =~ s/($re)/<$1>/g; # I added the ()'s :)
print $k;
[download]

Bah! It captures the outer square brackets too :(