This looks like it might be related to bookwork, so for the moment I'll just explore some possibilities.
In general I wouldn't hold much hope for a very useful bound, but by restricting it to binomial $(n,p)$ (sorry, I was working with $n$ in place of your $k$). I think it might be reasonably likely you can find something that will work pretty well.
In the case of the binomial, the population (standardized-third-moment) skewness is
$$\frac{1-2p}{\sqrt{np(1-p)}}$$
You could try rewriting your probability in terms of the pdf and the cdf.
You might like to consider the case where $E(X)$ is not an integer separately from the case where it is an integer (however, because of the way that the equality will be nonzero at the same time, the terms cancel, so things might simplify enough not to keep them separate).
Note that the cdf of the binomial is $\mathbb{P}(X \leq \mathbb{E}X)=\text{I}_{1-p}(n - k, 1 + k)$, (the regularized incomplete beta function) for which some approximations and bounds can be found, but there are also a variety of other bounds for the cdf.
One of these might allow you to relate such bounds to the skewness.