In the last Python releases, particularly 3.3 and 3.4, we've made improvements to the import machinery that render (at least) portions of pkgutil obsolete.  Here's a breakdown of the public API of pkgutil:

get_importer() - duplicate of PathFinder._path_importer_cache()
iter_importers() - yields the path entry finder for each path entry
find_loader() - a parent-importing wrapper around (deprecated) importlib.find_loader()
get_loader() - looks at module.__loader__ or calls find_loader()
walk_packages() - loader-focused
iter_modules() - loader-focused
get_data() - a wrapper around the InspectLoader.get_data() API
read_code() - duplicates importlib functionality
extend_path() - no longer needed (namespace packages)
ImpImporter - already deprecated in favor of importlib
ImpLoader - already deprecated in favor of importlib

I would expect that nearly all of the module could be deprecated and any gaps in functionality ported to importlib.util.

Is it worth it to go to the effort?  To me the biggest thing would be identifying what functionality (e.g. locating all packages within a directory) in pkgutil is still relevant and should be distilled into public APIs in importlib.  The job of actually deprecating and porting code would mostly be mechanical and not even a large amount of work.

Programmatic deprecation definitely isn't worth it - setuptools et al need this for cross-version compatibility with 2.x, and packaging tools are hard enough to write without us programatically deprecating things in 3.x releases.

Explicit documented deprecations where appropriate would be good, though.

I think programmatic deprecation is actually fine since that only comes up when running under -W which would be a bit odd for any tool to be run under except when testing. E.g. I had no personal issue deprecating imp for Python 3.4 even though that's the only way to do 2/3 programmatic import craziness as its use should be discouraged as much as possible since it's now fundamentally the wrong paradigm. And the tools can simply silence the deprecation if they actually find it noisy.

I do agree it should just be a PendingDeprecationWarning and not expect to remove it until either Python 4 or when the community has heavily shifted to Python 3. But when there are semantic replacements I think not doing a programmatic deprecation with warnings off by default is a disservice.