It depends on the exact nature of the deliverable.
I'm puzzled that you'd distribute them in paper full stop, actually, unless you've a client who insist that submissions for tender go through a paper process (not that rare in the public sector, actually). But the paper size depends on the exact reading context. Is this one person who's going to be reading this? Or are the paper copies going to be show to a group of people? For the latter, I'd see if I could get a cheap poster print.
Another thing: how detailed are these wireframes? I'm tempted to say that if they're detailed enough to require large sizes for readability, the wireframes could actually be over-specific on minor things (this just distracts stakeholders anyway). Depending on the stage of your project, a wireframe might just need to hint at the workflows rather than exact UI elements. These don't suffer from small printouts so much.
Be aware of print quality, too. White text on high-colour backgrounds is not only toner-heavy, but tends to blur on smudgy printers. Keep contrast high and colour variation low. Again, colour just distracts people unless it actually has semantic value. And a low-colour wireframe could help maintain readability at small sizes.