Debian and derived systems issue the message "You need to install the perl-doc package". On these systems, the package is called perl-doc and can be installed with sudo apt install perl-doc. This package includes the perldoc command, the POD files, and the manpages for Perl documentation.

If you build your own Perl, for example with perlbrew, then the perldoc program will be available for you, but not the manpages. So man perldoc won't work unless you build the man pages yourself.