If you don't have backreferences in your expressions, the actions of regular expressions are independent (as opposed to sequential) and your usage is sparse, you could precompile the world's ugliest regular expression:

my $main_re = do {
    local $" = ')|)(?=.*?(';
    my @REs = map $_->{from}, @conversions;
    qr/^(?=.*?(@conversions)|)/;
};
[download]

Called in array context, the result will be defined for all the indices where your regular expression matched. Thus allowing:

  my @scan = $entry{$k} =~ $main_re;
  for my $i (0..$#scan) {
    next unless defined $scan[$i];
    $entry{$k} =~ s/$conversions[$i]{from}/$conversions[$i]{to}/g;
    conversions[$i]{count}++;
  }
[download]

With backreferences, it's still possible but you'll have to map offsets. With dependencies between results, you could do something similar, but would have to map out Markov chains.

Probably more suggestions to be had with more details on the system.