Invert the logic. You want it only to match if all test cases match? Then make it fail if one doesn't match. It's an application of one of the two De Morgan's laws — case (r) in the table in section 2.3.1.1, here. You can only get through to past the end of the inner loop, if none of the tests failed.

The next code shows the idea, I've not actually run it (lack of data prevents that), but at least it compiles. It looks simple enough so it might work.

ROW: foreach my $row (@$list) {
    for my $i (0 .. $#vals) {
        unless ($vals[$i] && $row->[$i+1] &&
            String::Approx::amatch($row->[$i+1],
                                   $vals[$i])) {
            next ROW;
        }
    }
    # All succesful!
    return $row->[0];
}
# Boohoo... no match.
return;
[download]