Should I put core modules in the PREREQ_PM section of a Makefile.PL?

Question 1

Yes, you should specify all dependencies: The Perl Core is not fixed in all eternity. Core modules get added or removed (after a deprecation process) all the time. Specifying all your dependencies…

… will make your program work in future perls that have removed the module from Core. It will still be available from CPAN. For example Term::UI is a Core module since v5.9.5 but was removed in v5.19.0.
… will assert that a sufficiently high version of the core module in question is installed. Some modules have evolved significantly through time, and it is easy to forget that not everything was available five years ago.
… will make your program work on older perls that didn't include the module into Core, but are nevertheless able to use it.

On the other hand these can be very small gains. Nothing will break should you forget to specify such a central module like Carp as a dependency.

Remember: There are three causes for a module to be included in Core:

stuff central to Perl like strict which is not going to be removed.
stuff needed for downloading and installing CPAN modules. This includes filesystem handling. Here changes do happen occasionally.
Historic cruft. Pleeease throw out CGI.pm ;-)

Tip: use the corelist tool from Module::Corelist to see what modules versions are available in which perl release.

Question 2

There was an interesting discussion on this on PerlMonks not so very long ago.

My personal policy is not to do so.

Although modules are dropped from core occasionally, there is a long (about 2 year) deprecation cycle, giving you plenty of time to re-package your distribution with updated dependencies.

And if the worst comes to the worst, and you don't update your distribution, when they try to install it, they'll get an error message about a missing module, so it should be fairly obvious for them how to proceed. (That is, they should install that module, then try installing yours again.)