Can a Turing Machine decide if an NFA accepts a string of prime length?
The lengths of the strings accepted by a DFA form a semilinear set (like in Parikh's theorem for context free languages), the description of those isn't too hard to come by (essentially splice up all possible cycles of the automaton), and by Dirichlet's theorem any arithmetic progression of the form $a + b k$ with $\gcd(a, b) = 1$ contains an infinitude of primes.

Pulling the above together gives an algorithm to check if your regular (or even context free language) contains strings of prime length. Definitely not a simple question, IMVHO...