Finding a cycle of any *even* length can be found in $O(n^2)$ time, which is less than any known bound on $O(M(n))$. For example, a cycle of length four can be found in $O(n^2)$ time via the following simple procedure:

Assume the vertex set is $\{1,...,n\}$. Prepare an $n$ x $n$ matrix $A$ which is initially all zeroes. For all vertices $i$ and all pairs of vertices $j, k$ which are neighbors to $i$, check $A[j,k]$ for a $1$. If it has a $1$, output *four-cycle*, otherwise set $A[j,k]$ to be $1$. When this loop finishes, output *no four-cycle*.

The above algorithm runs in at most $O(n^2)$ time, since for every triple $i,j,k$ we either flip a $0$ to $1$ in $A$, or we stop. (We assume the graph is in adjacency list representation, so it is easy to select pairs of neighbors of a vertex.)

The general case is treated by Raphy Yuster and Uri Zwick in the paper:

Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J. Discrete Math. 10(2): 209-222 (1997)

As for finding cycles of odd length, it's just as David Eppstein says: nothing better is known than $O(M(n))$, including the case where $k=3$.

However, if you wished to detect *paths* of length $k$ instead of cycles, you can indeed get $O(m+n)$ time, where $m$ is the number of edges. I am not sure if the original color-coding paper can provide this time bound, but I do know that the following paper by some random self-citing nerd gets it:

Ryan Williams: Finding paths of length k in O*(2^k) time. Inf. Process. Lett. 109(6): 315-318 (2009)