Well, first off, I don't tend to use private methods all that much. I'll slap an underscore onto the start of a sub's name if I don't think it's likely to be useful outside of the current module, but I tend to think that hiding the internals is overrated, so I rarely do it, even at the "asking nicely" level. If I were working in a non-Perl language with a shotgun to enforce privacy, I doubt I'd ever use it.

When I do use private(ish) methods, I generally don't include them in any documentation, but "private" vs. "public" is not a factor in my testing. I test equally either way because my primary use for testing is to help me debug (present or future) problems and I find it useful to be able to localize the problem I'm debugging as quickly as possible. If A calls _B calls _C calls _D and _C breaks, I want my tests to be able to immediately tell me "there's a problem in _C", not "there's a problem in A" and then I have to manually look at A to see _B failed, then look at _B to see that _C failed, and probably also give _C a thorough going-over to be sure that _D didn't fail.