Jagged Paint edges

When I'm painting certain areas of my character sharply, I'm seeing jagged edges. Should I increase my texture size to 4096x4096 or make more than one uv set for my character to max texture quality?

Snapshot of the problem:

Current UV set:

 

It's often worth increasing the UV space of interest areas, particularly the head and face, and lowering the allocation for geometry that's less important or requires less detail in the final texture. Consider your camera angles, and where the eye is drawn to in play. It's easy to get caught up in every minutia angle when modelling and texturing, but in-game viewing is most important.

 

So what shells should I adjust or should I instead first move several shells to more uv squares (areas)?

 

With hero work (i.e. main character) I'd texture him up with separate UVs, in a spare UV channel with full high-res textures for each part. Then you're free to try out using a single UV map for the whole character with scaled parts, or multiple UV maps/textures, baking from the spare (hires) UV to (export/runtime) UV0 ... even different approaches for different platforms (i.e. one tpage/atlas for mobile, multiple for PC).

Which shells to adjust can be trial and error, but so long as you always have your source textures & materials mapped to the spare UV channel, you can always step back and try different approaches without losing work/time.