This is not really an answer as much as it is a caution that the problem, even with the extra assumptions I was able to solicit from the OP, is not going to have a very nice answer unless one adds some further hypotheses.
To see why, just look at the case that the dimension of the homogeneous space $M$ is equal to $2$. Even for $M=\mathbb{R}^2$ and $G$ is the group of Euclidean motions of the plane, there exists a huge family of Lagrangians on $TM$ such that the geodesics (up to parametrization) are the straight lines (basically two arbitrary functions of two variables worth of such Lagrangians, according to Darboux). Since, for this $M$ and $G$, each straight line is of the form desired by the OP, that means that there are many, many solutions to the problem, even in this simple case. (Note that most of these Lagrangians will not be invariant under $G$, even though the resulting geodesic path geometry is invariant under $G$.)
More generally, if $M=G/K$ is a surface endowed with just about any path geometry such that the (unparametrized) paths are all of the form $exp(tx)\cdot p$ for some $x\in \frak{g}$ and $p\in M$ and such that the set of paths forms a smooth surface of its own (and it is easy to construct many such examples), there will be a large family of nondegenerate Lagrangians on $TM$ whose geodesics are the curves in the path geometry. This family will depend on two arbitrary functions of two variables, though it will not be easy to write them down explicitly.
Thus, in my opinion, the question has too many solutions, even in the $2$-dimensional case, for there to be a good answer to the OP's question.