Compute the intersection of your CFG language with the regular language $\sum_{i=0}^k A^k$ (this amounts to multiplying the number of states by $k$ and adding a "dead end" state). Now check whether the result is empty: convert into a grammar (I think the result will have polynomial size) and "backtrack" from epsilon productions.
Edit: Kaveh mentioned that this is polynomial in $k$, so if $k$ is given as an input, the algorithm is exponential in $|k|$. However, Kaveh found a way to fix it. Convert the original automaton to a CFG, and replace all terminals by a fixed terminal. Now use an iterative algorithm to find the minimal size of a word generated by each non-terminal, as follows.
Initialize all lengths with $\infty$, and then iteratively update all lengths in the obvious way: given a production $A \rightarrow a^t \prod B_i$ (the order doesn't matter), put $f(A) = \min(f(A),t+\sum f(B_i))$. Claim: this converges in $O(n)$ iterations, where $n$ is the number of non-terminals. The reason is that in a tree generating the minimal-length word, no non-terminal is used twice; each "edge" takes at most one iteration to process (some edges can be "updated" in parallel).