If you use the /g modifier, you can use the pos function to find out where the match ended:

#!/usr/bin/perl -w

use strict;

my $str = "pencil
pen
marker
highlighter
pencil
pen
";

my $insert = "crayon\n";

while ($str =~ /pencil\npen\n/mg)
{
  my $pos = pos($str);
  substr($str,$pos,0) = $insert;
  pos($str) = $pos+length($insert);
}

print $str;
[download]