It is generally recommended to not use CPAN to install modules into the system Perl, because it's possible that if an installation fails, you might mess up your entire system, and cleaning that up can be a huge pain. Also, sometimes programs may rely on the system Perl having a specific version of a module and upgrading it may actually break those programs. Personally, I would recommend using perlbrew or plenv (or berrybrew on Windows) to install a fresh copy of Perl, or to use local::lib to install modules to the user's home directory. Both of these methods allow you to install any modules from CPAN you like, so when you look at it that way, it makes sense to just install everything from CPAN.

Also, do I understand correctly that it is recommended to prefer the CPAN modules instead of the OS ones ? I find this to be a real problem for any non-pure perl module, I belive the OS distro should be preferred in this case.

Well, CPAN will always give you the latest version of a module, while the OS repositories may have quite old versions of the modules (for example, that's the case on older Ubuntu LTS versions). On the other hand, once in a while building modules from source can be a pain, and if the distro has a precompiled version, just using that can be easier, so I see your point there. (BTW, if the problem is figuring out what libraries need to be installed for a Perl module to compile cleanly, on Debian/Ubuntu often sudo apt-get build-dep libwhatever-perl helps.) Another situation where I found it easier to install modules from the OS distro was on the first Raspberry Pi, where compiling stuff could take quite a bit of time. But other than that, I'd recommend using the CPAN version.

However, installing OS distribution packages is different for every operating system. ... This can get complicated when I need to install one module from CPAN, but some of the dependencies are available as OS packages

That sounds fairly ambitious to me. Have you actually run into this situation in practice?

I would like to show a message for users to install the needed perl modules when my script starts and dependencies are missing.

Have you had a look at lazy, or cpanfile, which can be used via cpanm --installdeps .? Another option is to distribute your script as part of a CPAN distro in the App:: namespace. As a regular CPAN dist, its dependencies are installed via the normal CPAN mechanisms. See e.g. ccdiff or ack. In combination with the above suggestions of perlbrew or local::lib, this should allow you to easily install any CPAN dependencies.

see if a package like libModule-Name-perl is available in the repos.

That naming convention isn't always kept though, for example LWP is in libwww-perl. You might need to do something like apt-file search --regex '/Module.pm$', although then figuring out e.g. all the different */Tiny.pm modules might be difficult. (BTW, I recently wrote a script to try and use the MetaCPAN API to figure out modules' dependencies, maybe the CPAN distro names can help in figuring out the package names.)

So anyway, my personal recommendation would be to use one of the methods I mentioned above that allow you to install anything you like from CPAN. However, all of those suggestions involve compiling the dependencies. So it seems to me that this comes down to another question: Which modules specifically are you having trouble compiling?