Say $M$ has start state $s$ and transition function $\delta$. Construct a new Turing machine $M'$ with $Q = \{s, HALT\}$ (where s != HALT) and $\delta'$ as it's transistion function, defined by the following. $s$ is again the start state and $HALT$ is the accept state.
$$ \delta'(s, x) = \begin{cases}
s & \delta(s, x) = s \\
HALT & \mbox{otherwise} \\
\end{cases} $$
$M'$ will halt IFF $M$ ever transitions out of the start state.
If you know what the maximum shifts function is for two states and your symbols then you can simulate $M'$ for that many steps to determine if $M'$ halts or not. Non constructively even if we can't compute the busy beaver function for your number of symbols it has some value and therefore our argument still goes through.
This shows that, at least classically speaking, this problem is decidable. It also constructively shows that it's decidable for any number of symbols that we can constructively prove an upper bound on the maximum step function for. This algorithm runs in constant time...where the constant might be very large. So asymptotically it's ideal. I'm not sure if there's an algorithm that does this with a smaller constant but I'm betting it's not possible.