I rewrote the code to make it work as described in your post.

replace_with_matches.pl

#!/usr/bin/perl

use warnings;
use strict;

my $source = shift @ARGV;
my $destination = shift @ARGV;
my $matchfile = shift @ARGV;



my @matches = ();

open (MF, '<', $matchfile) or die $!;
while (<MF>)
{
    push @matches, $_;
}
close MF;


# have a list of all matches





my @input = ();

open (IN, '<', $source) or die $!;
while (<IN>)
{
    push @input, $_;
}
close (IN);




# have all input lines in an array



my @output = ();

NEXT_INPUT_LINE:
for my $input_line (@input)
{
    
    # check every input line 1 time


    NEXT_MATCH_PAIR:
    for my $match_pair (@matches)
    {
        my @DATA = split (/\s/, $match_pair);
        my $matcher = $DATA[0];
        my $replacer = $DATA[1];
        
        
        # check all match pairs against 1 input line
        
        if ($input_line =~ /^$matcher/)
        {
            # make replacement
            $input_line =~ s/legend/$replacer/;
            push @output, $input_line;
            
            # jump to next input line
            next NEXT_INPUT_LINE;
        }
    }
    
    # if it gets here, there was no replacement
    
    
    # copy input line to output
    
    push @output, $input_line;
}




# have all replaced output in @output





# write @output to $destination


open (OUT, '>', $destination) or die $!;
for my $output_line (@output)
{
    print OUT $output_line;
}
close OUT;

[download]

Sample input files:

source.txt

lancer is a legend asdf
asdfwerg asdf wergdfv legend
pieces of trash
line 4 is cool and makes no sense
time for legends
time for christmas 
jesus is a legend

[download]

matches.txt

l jerk
j myth

[download]

Sample output:

result.txt

lancer is a jerk asdf
asdfwerg asdf wergdfv legend
pieces of trash
line 4 is cool and makes no sense
time for legends
time for christmas 
jesus is a myth

[download]