I think that the correct route is very environment specific, but that in general I would lean heavily toward a Perl-centric interface. There are, as you note, distinct advantages to each route.
If the module is apt to be a performance bottle neck, then you may be right to sacrifice Perlisms on the alter of efficiency. This is the case for modules that are either going to be used mostly in house, and so you don't care about adoption by the community at large of your (perhaps ugly) library, or because it is a common performance bottle neck for lots of applications and so people are willing to surmount the barrier to entry.
In general, though, the human factor is a much bigger consideration than the machine factor. When pulling a module off of CPAN, people typically want something that will get their job done quickly and easily... from the perspective of man-hours. They don't want to have to suss out an arcane interface. Employing common idioms in your library API will help prevent potential users from getting frustrated and seeking out an alternative. Oft times when I'm examining a module for potential use, I cast initial judgment within minutes of glancing over the documented API. If it looks unnecessarily cumbersome, I'll probably say "screw it" and move on, unless the module's functionality is extremely important to me and there are no other viable alternatives.