You can do this by following the logic in a FAQ: How do I compute the difference of two arrays? How do I compute the intersection of two arrays?. Essentially, this creates a hash with keys that correspond to the entries of @lines. You can then use that hash to check if the entries existed:

#!/usr/bin/perl
use strict;
use warnings;

my %hash = ("One","1","Two","2","Three","3","Four","4");
my @lines = ("One", "Two", "Three");

my %count;
foreach my $element (@lines)
{
    $count{$element}++;
}

foreach my $i (sort {$hash{$a} <=> $hash{$b}} keys %hash)
{
    if (exists $count{$i})
    {
        print "$i,$hash{$i},Hit\n";
    }
    else 
    {
        print "$i,$hash{$i},Miss\n";
    }
}
__END__
One,1,Hit
Two,2,Hit
Three,3,Hit
Four,4,Miss
[download]

Your output lines are also much more complex than they need to be; see Quote and Quote like Operators. As well, you don't need to stringify to use something as a hash key - Perl does that automatically. Compare your output lines to the ones I have above.