There might be more categories, in which case putting each one in your regex is inefficient. It's much better to just match on any word string for category. Also, lowercasing your item name should be more efficient than using the i flag, unless your list of items is very small.

use strict;
use warnings;

my $scalar = "::fruits||apple::fruits||orange::vegetable||celery::vege
+table||lettuce";
my $word = "Celery";

$word = lc $word;
$scalar =~ s/::\w+\|\|$word//g;

print $scalar;
[download]

If of course you'll be doing many changes to the list in a single run, you'll want to convert it to nested hashes:

use strict;
use warnings;
use Data::Dumper;

my (%hash, $cat, $item);
my $scalar = "::fruits||apple::fruits||orange::vegetable||celery::vege
+table||lettuce";
my $word = 'Celery';

$scalar =~ s/^:://;
for (split /::/, $scalar) {
    ($cat, $item) = split /\|\|/;
    $hash{$cat}{$item} = ();
}

$word = lc $word;
for $cat (keys %hash) {
    delete $hash{$cat}{$word} if exists $hash{$cat}{$word};
}

print Dumper(\%hash);

$scalar = '';
for $cat (sort keys %hash) {
    for $item (sort keys %{$hash{$cat}}) {
        $scalar .= "::$cat||$item";
    }
}

print $scalar;
[download]