Rearranging multiple objects is a critical skill for robots so as to effectively deal with clutter in human spaces. The challenge arises from combinatorially large, continuous C-spaces involving multiple movable bodies and complex kinematic constraints. This work proposes hierarchical frameworks for efficiently solving prehensile object rearrangement with a robotic manipulator. Useful rearrangement primitives are identified for solving certain classes of problem instances, which are then composed by higher-level task planners. Using more powerful primitives, which are reasoning about the underlying combinatorial and multi-object nature of the problem, are shown to be beneficial in the context of such hierarchical schemes.