AUTOLOAD is not obsolete, especially if you're using it for generally "unknown" methods. The "usual" implementation of an AUTOLOAD subroutine then generates and installs the code (well, subroutine) to handle the specific case:

sub AUTOLOAD {
    my $method = $AUTOLOAD;
    my $handler = sub { ... };
    # Install the handler:
    no strict 'refs';
    *{ $method } = $handler;
    goto &$handler;
}
[download]

OK, good to know. But how I properly document in my POD? Is there a standard practice for this? The methods are dictated by the user who is using his own custom classes so there is no way for me to know what these methods are going to be actually named.

$PM = "Perl Monk's";
$MCF = "Most Clueless Friar Abbot Bishop Pontiff Deacon Curate Priest Vicar";
$nysus = $PM . ' ' . $MCF;
Click here if you love Perl Monks

I would try document the behaviour. Maybe something like:

=head1 Handling of file classification

For every file category as found via C<< ->find_categories >>,
the module provides a function C<< find_FILE_CATEGORY_files >>.
In the below example, the C<< get_cats_files(...) >> function returns
all files in the C<< cats >> category:

    my $cat = find_category_for_file( 'myfile_cats.txt' );
    # cats
    print for get_cats_files('/*');
    # myfile_cats.txt myfile2_cats.txt ...
[download]

Personally, while AUTOLOAD is enticing, why not make the category a real parameter instead? Otherwise, the programmers will have no good way of passing an arbitrary category to your code.