Perl 5.8以降なら

use encoding "euc-jp";

my $a = "\xcb\xcc\xb4\xd8";
my $b = "\xcc\xb4";
print ($a =~ /$b/ ? 'OK!' : 'NG!');

--
String::Multibyteをインストールするなら

use String::Multibyte;

my $euc = String::Multibyte->new('EUC_JP');
my $a = "\xcb\xcc\xb4\xd8";
my $b = "\xcc\xb4";
print ($euc->index($a, $b) >= 0 ? 'OK!' : 'NG!');

--
自力で解決

my $a = "\xcb\xcc\xb4\xd8";
my $b = "\xcc\xb4";
my $euc = "^(?:[\x00-\x7e]|\xfe?[\xa0-\xff][\xa0-\xff]|\x8e[\xa0-\xff])*";
print ($a =~ /$euc$b/ ? 'OK!' : 'NG!');