The reason your @animals array never changes after the first loop is because the @animals array has changed to the point that it doesn't HAVE the <1> tags in it anymore. If you didn't use a reference to the elements of the array, you'd be fine:

print map( change($_, \@toFind, \@toChange), @animals );
...
sub change {
  my $str = shift;
  ... {
    $str =~ ...
  }
  return $str;
}
[download]

But your loop is dangerous. What if <1>'s "change to" value happens to be this <3> thing? You need to figure out if you want recursive (or chaining) replacements to be allowed. Here's how I'd approach the matter:

# replace($string, \@from, \@to, $allow_recursion)
# recursion is turned off by default

sub replace {
  my ($str, $from, $to, $recurse) = @_;

  # set up a hash for easy lookup
  my %replace;
  @replace{@$from} = @$to;

  # this is the safe way to create a regex
  # alternation of the possible "from" strings
  my $from_rx =
    join '|',
    map { quotemeta }
    sort { length($b) <=> length($a) }
    @$from;

  # compile the regex
  $from_rx = qr/($from_rx)/;

  # this handles non-recursion
  # as well as recursion... you
  # might consider this a hack
  do {
    $str =~ s/$from_rx/$replace{$1}/g
      or $recurse = 0;
  } while $recurse;

  return $str;
}
[download]