One statement:

$_='A # B # 1 # 2';
print
  join ' # ',
    sub { map @_[$_,$_+@_/2], 0..$#_/2 }->(
      split / # / 
    );
[download]

More readable:

sub pair { map @_[$_,$_+@_/2], 0..$#_/2 }

$_='A # B # 1 # 2';
print join ' # ', pair split / # /;
[download]

I didn't see the purpose of avoiding split — you didn't say what you didn't like about it — but you could replace
split / # /
with
/(?:(?! # ).)*/sg