This paper introduces a new method for robot motion planning and navigation in uneven environments through a surfel representation of underlying point clouds. The proposed method addresses the shortcomings of state-of-the-art navigation methods by incorporating both kinematic and physical constraints of a robot with standard motion planning algorithms (e.g., those from the Open Motion Planning Library), thus enabling efficient sampling-based planners for challenging uneven terrain navigation on raw point cloud maps. Unlike techniques based on Digital Elevation Maps (DEMs), our novel surfel-based state-space formulation and implementation are based on raw point cloud maps, allowing for the modeling of overlapping surfaces such as bridges, piers, and tunnels. Experimental results demonstrate the robustness of the proposed method for robot navigation in real and simulated unstructured environments. The proposed approach also optimizes planners' performances by boosting their success rates up to 5x for challenging unstructured terrain planning and navigation, thanks to our surfel-based approach's robot constraint-aware sampling strategy. Finally, we provide an open-source implementation of the proposed method to benefit the robotics community.