... store regexes and substitutions in the same array, but distinguished by different indexes ...

An example of what I think moritz is referring to (and the way I think I would approach the problem):

>perl -wMstrict -le
"my @subs = (
   [ qr{ (?i)  foo | bar }xms => 'quux' ],
   [ qr{ fee | fie | foe }xms => 'fum'  ],
   );
 ;;
 my $string = 'foo fee BAR foe fOo fie FOE';
 for my $ar_sub (@subs) {
   my ($search, $replace) = @$ar_sub;
   $string =~ s{$search}{$replace}g;
   }
 print qq{'$string'};
"
'quux fum quux fum quux fum FOE'
[download]

Note that regex modifiers like /g cannot be associated with each individual regex using this approach; something a little more fancy is needed for that.