This work addresses the problem of whole-body motion planning for a humanoid robot that must execute a certain task in an environment containing obstacles. A randomized planner is proposed that builds a solution by concatenating whole-body motions. Each whole-body motion is generated so as to realize a center of mass (CoM) movement selected from a set of primitives and simultaneously accomplish a portion of the task. The CoM primitives are representative of typical humanoid actions such as walking gaits (static and dynamic), and can in principle include more sophisticated movements (e.g., jumping, crouching, etc). Implementation on the NAO humanoid proves that the proposed method generates sensible plans for a variety of composite tasks requiring a combination of navigation and manipulation.