A dh_usrlocal manpage pode ajudar você a entender o que está acontecendo.
Pacotes Debian têm permissão para instalar diretórios sob /usr/local , mas a melhor maneira de fazer isso é usar scripts de mantenedor. dh_usrlocal automatiza isso transformando diretórios em /usr/local em trechos de script do mantenedor. Ele assume que esses diretórios estão vazios, já que os pacotes Debian não têm permissão para instalar arquivos em /usr/local .
Em seu pacote, dh_install segue suas instruções e copia app-cli para /usr/local/bin (dentro do seu pacote). dh_usrlocal é executado, vê o diretório, cria o script de mantenedor apropriado e tenta excluir o diretório (por isso, ele não é fornecido como tal no pacote) - e falha, pois contém um arquivo.