This seems reasonably efficient to work:/

Update:I screwed up my benchmark, this is way slow compared to your method.

#! perl -slw
use strict;

my %lookup = ('{'=>'}', '('=>')', '['=>']', '<'=>'>');
my $re_q = qr[\bq(.)(.*?)(?<!\\)(??{ $lookup{$1}||$1 })]so;

my $string = do{ local $/; <DATA>};
print "Match:'$2'" while $string =~ m[$re_q]g;

__DATA__
my $km = q'BEGIN simple foo bar baz END';
my $kv = q#BEGIN foo bar \# baz END#;
my $kk  = q{BEGIN super foo bar
              banzai END};
my $kt  = q{BEGIN super foo \{super\} bar
              banzai END};
[download]