"He has a headache and he needs to rest."
Apart from the 很issue discussed here (I'm also pretty sure it doesn't need to be used here), the particle 的 can also be omitted when referring to body parts: 我头疼, 他肚子不舒服, 我腿麻了etc
"他的头很疼，他需要休息" Marked wrong as of 2019-02-19. Reported.
Redundant 他 might not be necessary, but it shouldn't make it wrong.