I don't know whether CPAN has a no-binary policy (if you really going to include compiled binaries :), I tried to look that up but couldn't find anything. So I would like to forward that question to other monks :) But executable Perl scripts should be no problem at all.

About files: yes, putting the executables in a special directory will work, eg. exe/ or bin/. But note: If you want that exe to be installed with your module you have to adjust Makefile.PL (or Build.PL, or whatever you use for your module).

If my module comes with executable scripts I usually put them in a bin/ directory and adjust the Makefile.PL like this (I'm using MakeMaker):

use strict;
use warnings;
use ExtUtils::MakeMaker;

WriteMakefile(
    NAME                => 'BS',
    # ...
    EXE_FILES           => [qw(bin/bs bin/bsxmpp bin/bsirc bin/bshttp 
+bin/prelay bin/bslogparse bin/bsconf)],
    #...
);
[download]

With that the scripts/binaries are installed when the module is installed. I hope this helped a bit?