What is the VC dimension of Turing machines with specified maximum size? Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.

I chose Turing machines in the question to make the question concrete, but I'm also more generally interested in known VC bounds for Turing-complete languages with a limit on the program length (to avoid infinite vc dimension).

The closest I've seen is this article giving VC dimension for recurrent neural nets, which can be Turing complete, but have finite VC dimension in terms of the number of weights and the length of the inputs.
The exact VC bounds will depend on the alphabet size and the exact specification of the transition function (must it always move left or right, or can it stay put, etc). For fixed alphabet size, say 2, I think you can apply the DFA-VCdim analysis of


  Ishigami and Tani, VC-dimensions of finite automata and commutative finite automata with $k$ letters and $n$ states, Discrete Applied Mathematics 74 (1997), no. 3, 229-240


to show that the VC-dim of $n$-state TM's will be $\Theta(n\log n)$.

Those other VC bounds you mentioned in terms of the NN connection weights are more in the spirit of SVM bounds in terms of the norm of the separating hyperplane.

Update: Here's a proof sketch. For a fixed alphabet size (say, 2) and $n$ states, there are $n^{cn}$ transition functions from (state,letter) to (state,letter,head move), where $c$ is a universal constant. Taking logs gives you a VC upper estimate of $O(n\log n)$. The lower bound comes from the Ishigami-Tani analysis, since an $n$-state DFA can be realized as an $n$-state TM (plus $n$ additional bits to indicate which states are accepting, but this is negligible compared to the $n^{cn}$ factor).