I found out that Net::LDAP::Control::Paged is not supported under the Sun Directory Server (formerly iPlanet Directory Server). I don't know about W2K AD, but suspect it is supported. If you don't receive a timely reply here you might try joining the perl-LDAP mail list since they specialize in the Net::LDAP modules.
in reply to NET::LDAP (with Page control) error 83 returned from W2k search
You can verify whether it is supported or not by adding critical => 1 into the arguments for the Net::LDAP::Control::Paged->new statement.
Update: After looking more closely at your code, it appears you haven't used the Paged->new method or defined $page. If you'd been using "strict" and "warnings" it would have been pointed out to you. You should clean up your code and include something similar to the following before you use the $page variable:
my $page = Net::LDAP::Control::Paged->new( size => 5 );