We generalize geodesic finite elements to obtain spaces of higher approximation order. Our approach uses a Riemannian center of mass with a signed measure. We prove well-definedness of this new center of mass under suitable conditions. As a side product we can define geodesic finite elements for non-simplex reference elements such as cubes and prisms. We prove smoothness of the interpolation functions, and various invariance properties. Numerical tests show that the optimal convergence orders of the discretization error known from the linear theory are obtained also in the nonlinear setting.