Yes, but he uses Occam’s Razor.
“Shaves all” can mean… shaves everywhere, as in naughty bits, etc. rather than ‘shaves everyone’. He does not shave himself because he doesn’t shave those who shave themselves. Whether he is even shaven or not is not relevant – either he goes unshaven or has his slave do it for him.
I don’t see the paradox.
Making the barber a woman doesn’t resolve the situation. She still either shaves or doesn’t shave herself. This barber, as described, has to shave women and children and those without body hair–anyone who doesn’t shave themselves.