(Toby Bartels wrote back, explaining that he was having some trouble logging in to his account here, but asking if I could post some comments he had. I'm going to post them under my name as Community Wiki, and invite him to edit this answer further once he's back, if he'd like -- or he can post separately of course.)

I believe that local smallness follows (in conventionally strong foundations) from the other axioms (this is what the Elephant seems to say in C.2.2.8.vii), so the right thing to do should just be to remove it from the list of axioms, which I have now done at the nLab. However, it would be good to have the argument written out in a clearly predicative way, to be certain. I no longer have access to my copy of the Elephant (I had to check the wording of C.2.2.8 in Google Books), which I believe was my guide the last time that I was thinking through this, but hopefully I can find it in the library and extract an explicitly predicative and constructive argument from its proofs.

More speculatively, the classical proof that Giraud's axioms imply local smallness might have a strongly predicative variation proving, say, that there is a small generating set (possibly smaller than the original one) $G$ such that $\hom(G,X)$ is small for each $X$. That solves your problem of getting a Set-valued sheaf from an object, and it's trivial (but impredicative) to prove that a category with such a generating set must be locally small. But I'm not sure that it's actually correct!