I wanted this to be a comment since I don't know enough probability to finish the argument but it was a bit too long:

You can transform the positions of the stones into the following data - one number telling us the position of the center of mass of the inchworm, and a $(k-1)$-tuple of positive integers $\vec{a}=(a_1,\dots,a_{k-1})$ living in the hypercube $C$ defined by the inequalities $1\leq a_i\leq d$ which correspond to the distances between each pair of neighboring stones.

Each step of your process is a trial move of some random stone either left or right.  This corresponds to some trial move of $\vec{a}$, where some component(s) will be incremented or decremented.  I tried to define $C$ so that your conditions (a) and (b) precisely correspond to $\vec{a}$ staying within a "configuration space" $C$ of the body of the inchworm. Provided $\vec{a}$ does not attempt to leave $C$, the center of mass of the inchworm will move a distance of $1/k$ either left or right.  

Thus the problem boils down to understanding how $\vec{a}$ moves around $C$ and in particular how often it attempts to leave $C$.  In particular a good bound on this event will tell us how often the center of mass is _not_ behaving like a simple random walk.

-------

I wrote some Mathematica code for playing around with this model.  It's at the end of this answer.

Here is a picture of a run for the case $k=3$, $d=2$ as described in Douglas Zare's comment above. The different colors correspond to different stones.

![inchworm k=3 d=2][2]

While it is true that in the first step the center of mass will tend to move left there isn't any particular propensity for the worm to move left or right in the long run.

![inchworm k=3 d=2 center of mass][1]


The configuration space for a worm with $k=3$ is a $d$ by $d$ square. Here's a histogram of the time spent at each point from a run of $10^5$ steps with $k=3$ and $d=10$.  It seems that the inchworm spends an equal amount of time in each possible configuration.  This should follow from basic results on random walks on finite graphs but I don't know them.

![configuration space histogram][3]

It seems that the amount of time that the center of mass is "stuck" because $\vec{a}$ attempts to leave $C$ is proportional to $1/d$ which intuitively seems to come from dividing the area of $C$ by its volume.

------
    n = 100000;
    a0 = {0, 1, 3};
    a = a0;
    k = Length[a];
    inputrand = 
      Table[{RandomChoice[{-1, 1}], 
        RandomChoice[Table[i, {i, k}]]}, {n}];
    d = 2;
    happening = 
      Table[j = inputrand[[t, 2]]; 
       anew = a + Table[If[ind == j, inputrand[[t, 1]], 0], {ind, k}];
       If[(j == 
            1 || (anew[[j]] > anew[[j - 1]] && 
             anew[[j]] - anew[[j - 1]] <= d)) && (j == 
            k || (anew[[j + 1]] > anew[[j]] && 
             anew[[j + 1]] - anew[[j]] <= d)), a = anew];
       a, {t, n}];
    happening = Join[{a0}, happening];
    ListPlot[Table[happening[[All, i]], {i, k}], Joined -> True]
    ListPlot[Table[Mean[happening[[t, All]]], {t, n + 1}], Joined -> True]


  [1]: http://i583.photobucket.com/albums/ss275/jaspercrowne/inchwormcm32_zpsd5623ee7.png
  [2]: http://i583.photobucket.com/albums/ss275/jaspercrowne/inchworm32_zps908fefa5.png
  [3]: http://i583.photobucket.com/albums/ss275/jaspercrowne/configspace_zpsbb4e874f.png