1. Exercises, puzzles and projects all have one major theme in common: they are all a legitimate approach to solving math problems. However, while they may all get you the same answer to a math problem, they are three VERY different approaches, in my opinion.
When I hear the term math "exercises" I think of your basic, daily math problems that you independently solve. When you physically exercise, you focus in on a particular muscle in your body that you want to strengthen and you work it out a little to do just that, strengthen it. Same thing with math exercises. Maybe one day you want to strengthen your multiplication skills so you do 25 multiplication problems. You may show your work, you may not. Your simply exercising and strengthening a skill you already have, so showing your work may not be neccessary.
Math "puzzles" are more in depth then just exercises. Math puzzles may demand things from you that you're not typically used to exercising (thus differentiating it from math exercises) or perhaps it expects you to utilize the combination of several of your math skills to come up with the answer. It's usually a problem with a longer process then simply a math exercise. Like when you're playing with an actual puzzle, you have to put all of the pieces together to get the result: a complete picture. Same thing with math puzzles, you're expected to put several math skills (or puzzle pieces) together to come up with the solution (or the completed puzzle with a picture).
Math "projects" are even more in depth then puzzles. When I think of a math project, I don't think of just solving a math problem, I think of looking into the problem, figuring out WHY the answer is whatever it is. For example, instead of simply saying that 4x3=12 (which would be just a math exercise), a math project based on the concept of 4x3=12 would expect the student to explain the process of how you come to the conclusion of 4x3=12.
2. Problem solving is the process of looking at a problem and coming up with a solution to it. What process one uses to come up with the solution depends on the student and what kind of learner they are and if they understand the problem. Therefore, I think, that what can be cut out of a problem solving process really depends on the student. For example, looking at the problem of 10x3=?, if a student knows off the top of their head that 10x3=30 then, great, problem solved. They can cut out the actual process of coming to this conclusion. However, if a student needs to cross multiply to come up with the answer, then they can cut out the process of counting by 10's on their fingers. Or, maybe, a student needs something more visual and needs to draw 10 sets of 3 tally marks and then count up all the tally marks to understand. Therefore, they can cut out cross multiplying. Basically, what I'm trying to say is that unneccessary procedure when problem solving should definitely be cut out if there are time restraints, however, what exactly that "unneccessary procedure" is really depends on the student.
3. Yes, I believe that kids of any age can be engaged in mathematical problem solving because I believe that mathematical problem solving is exercised by humans from day one, even before they are aware of what "math" really is. For example, I work at a preschool and I am often in the infant classroom. For snack I may give them cheerios and David constantly throws most of his cheerios on the floor the minute I put them on the tray of his high chair by waving his hands back and forth through the pile of cereal. To prevent him from doing this, I've started only putting three cheerios at a time on his tray. He sees that he has less and he doesn't want to throw them on the floor because he thinks that's all he's going to get and if he throws any on the floor he won't have any to eat. Of course, once he eats the three cheerios I give him three more until he is done eating, but he doesn't realize this. What he does realize, though, is that I've started giving him less cheerios then normal so he therefore doesn't throw them on the floor. This simple realization of what is less and what is more is math right there, a basic form of it, but it's his math skills developing none the less.