One way to do it is the (?{ collect() })(*FAIL) trick

use v5.12;                              # https://perlmonks.org/?node_
+id=11146744
use warnings;
use Data::Dump qw/pp dd/;

#pp
my ($paths,$cmds) = data();

my $re = join "|",
  map {"\Q$_\E" }
  @$paths;


for my $cmd (@$cmds) {
    my @matches; 
    $cmd =~
      m{
           ^CMD="
           ($re)
           #/?                          # final / is missing
           (?!\.)                       # no empty name before .extens
+ion
           ([^/]+)
           "$
           (?{push @matches,[$1,$2]})
           (*FAIL)
         }x;
    pp {$cmd => \@matches};
}



sub data {
    return [ qw(
/a
/a/b
/a/b/c
/b
/b/c
/c
/ab
/abc
/abcd
          )]
      ,
        [ qw(
CMD="/a/a.sh"
CMD="/aa.sh"
CMD="/ab.sh"
CMD="/abc.sh"
CMD="/a/bc.sh"
CMD="/a/b/c.sh"
CMD="/a/b/c/.sh"
CMD="/a/b/cd.sh"
CMD="/a/b/c/d.sh"
CMD="/x/y.z"
CMD="/a/xyz.sh"
CMD="/abcd.sh"
        ),
          q(CMD="/a/very 'special' command.exe")
     ]
    }
[download]

But while my results are in sync with

>

QRY(4)="/a/bc.sh"
QRY(4)="/ab/c.sh"
[download]

they differ significantly because my understanding is that the OP said that all CMDs have a missing final slash. I also disallowed files starting with a dot like .sh

{ "CMD=\"/a/a.sh\"" => [] }
{ "CMD=\"/aa.sh\"" => [["/a", "a.sh"]] }
{ "CMD=\"/ab.sh\"" => [["/a", "b.sh"]] }
{ "CMD=\"/abc.sh\"" => [["/a", "bc.sh"], ["/ab", "c.sh"]] }
{ "CMD=\"/a/bc.sh\"" => [["/a/b", "c.sh"]] }
{ "CMD=\"/a/b/c.sh\"" => [] }
{ "CMD=\"/a/b/c/.sh\"" => [] }
{ "CMD=\"/a/b/cd.sh\"" => [["/a/b/c", "d.sh"]] }
{ "CMD=\"/a/b/c/d.sh\"" => [] }
{ "CMD=\"/x/y.z\"" => [] }
{ "CMD=\"/a/xyz.sh\"" => [] }
{
  "CMD=\"/abcd.sh\"" => [["/a", "bcd.sh"], ["/ab", "cd.sh"], ["/abc", 
+"d.sh"]],
}
{ "CMD=\"/a/very 'special' command.exe\"" => [] }
[download]

YMMV, but other interpretations of the OP are easily implemented by (un)commenting the two documented lines in the regex.

update

           /?                            # final / is missing
           #(?!\.)                       # no empty name before .exten
+sion
[download]