Algorithm for fewest number of moves with artificial minimum
We construct a directed graph $G'$ with $V'=V \times \{0, \dots, k\}$ when $k$ is the lower bound on the path length.
For every edge $uv$ in $E$ and $i&lt;k$ we add $(u,i)(v,i+1)$ and $(u,k)(v,k)$ to $E'$.

Now we search for a shortest directed path from $(s,0)$ to $(t,k)$ in $G'$ to find the shortest path from $s$ to $t$ in the original graph $G$. 

The digraph $G'$ has $(k+1)n$ vertices and $(k+1)m$ edges. Hence, the running time is still polynomial 

Searching for the shortest odd (or even) path works similarly. Indeed I think that any regular (as in NFA recognizable) constraint on the path can be solved like that.

Edit:
Note that the second entry in the tuples stays the same. To be more precise, consider any path $P=v_0v_1…v_kv_{k+1}…v_n$ on $G$ with length $≥k$. Then there is a corresponding path $P'=(v_0,0)(v_1,1)…(v_k,k)(v_{k+1},k)…(v_n,k)$ on $G'$.
Similarly, every path on $G'$ induces a path on $G$.