For your first question, you could avoid the regex match entirely by using substr and index, writing

CHUNK:
while ( ( my $pos = pos $sentence ) < length $sentence ) { 
    for my $phrase ( @phrases ) {
        if ( my $index = index($sentence, $phrase ) >= $pos ) {
            my $length = length $phrase;
            substr($sentence, $index + $length, 0, '#');
            substr($sentence, $index, 0, '#');
            pos $sentence = $index + $length + 2;
            next CHUNK;
        }
    }
    last CHUNK;
}
[download]

For the second question, split has no way of knowing what you want the stuff between the separators to be; but you could make the phrases themselves the 'separators', and capture them:

my @split = split /($phrase1|$phrase2)/, $sentence;
@phrases = @split[map { 2 * $_ + 1 } 0 .. ($#split - 1)/2];
[download]

This works because leading empty fields are preserved, so the separators are in the odd-indexed fields. I'm sure there's a better way to get just the odd-indexed fields, though.

UPDATE: Fixed my code to put # after as well as before. Also, I misunderstood your original question to mean that the regex matching itself was too slow, rather than that making up a bunch of regexes was too slow. kyle's solution is probably faster.