Age of the child learning to sew is not the issue...interest is! And they must be both interested in sewing and interested in the project. It is also important to have something that they can finish quickly and see results to be proud of.
The suggestion to have several choices of initial projects is a good one. It is also helpful to have several fabric choices as kids have their own color and design preferences just like we do...sometimes very definite thoughts on such things at a very young age.