It's a good time for a hash and grep.

my %delh;
@delh{@dels} = ();
@array = grep ! exists $delh{$_}, @array;
[download]

List::Compare's get_unique member may help.

use strict;
use warnings;
use List::Compare;

my @array=('water','wine','apple','beer','orange');
my @dels=('apple','orange');
my $lc = List::Compare->new( { lists => [\@array, \@dels] } );

print join ', ', $lc->get_unique ();
[download]

Prints:

beer, water, wine
[download]

For some definition of "matches", the basic algorithm is

my @out;

for my $i (@in) {
   my $delete = 0;
   for my $d (@dels) {
      if (matches($i, $d)) {
         $delete = 1;
         last;
      }
   }
   push @out, $i if !$delete;
}
[download]

In your original question, you asked for equality, so "matches($i, $d)" would be "$i eq $d".

In your updated question, you asked for substring presence, so "matches($i, $d)" would be "index($i, $d) >= 0" or "$i =~ /\Q$d\E/".

The hash solution and the build-a-regexp solution are simply optimizations of the above algorithm.

You want to lookup if something is in the list of items to delete. Hashes are good for looking up strings.

my %dels = map { $_ => 1 } @dels;
@array = grep !$dels{$_}, @array;
[download]

use Data::Dumper;
my %hash=(water => 1,
    wine => 1,
    applepie => 1,
    beer => 1,
    orange => 1,
    juice => 1
);
print Dumper \%hash;
@dels=('applepie','orange');

foreach (@dels)
{
    delete $hash{$_};
}
print Dumper \%hash;
[download]