No loops and just one regular expressioon:

use Modern::Perl '2014';

my $first  = qr/STRING/;
my $second = qr/MAGIC/;

my $corpus = join '', map { chomp; $_ } <DATA>;

if ( $corpus =~ m/($first)(?!.*$first).*($second)(?!.*$first)/ ) {
    say "Success: $-[1] and $-[2]";
}
else {
    say "Failure";
}

__DATA__
First line
second line
here is the STRING
empty text
the STRING again!
followed by the  MAGIC word
more emptiness
Oh no! the first STRING again
sadness
did we look in vain?
Yes, It's like MAGIC
we are happy
Ah, STRING and MAGIC success
MAGIC and STRING failed
[download]

Fiddle around with the DATA-section to check the various possibilities and combiinations.