I think you could find some insight in this bulletin by Gorard. There, he analyzes a system quite similar to yours, namely the rule {X0->0X, 0X->X0} starting from a string like 00000X00000, which is essentially your random walk, but forced to move right or left each step.
In the bulletin, to each state it is assigned a real number, that is proportional to the number of different paths that can lead to the state. In this way Gorard is able to show the effect of diffraction, so it doesn't seem that this kind of system can exhibit interference patterns (I think that when you refer to a quantum random walk, you mean that you would like to see an interference pattern emerge).
So how do we get interference? Gorard's answer is to start from a different initial condition: if you start with something like 000000X000X00000, with two Xs, you get a peculiar interference pattern.
In the second part of the paper Gorard explains how all this is connected with his paper on quantum mechanics. I couldn't understand many parts of it, but I'd like to discuss it with you.
In particular, I would like to quote the following, which I think could be helpful in understanding how to calculate the phase of the action along a path:
So how does a completion procedure achieve the destructive interference effects that are so crucial for reproducing the results of the double-slit experiment just shown? As I described in my quantum mechanics paper, the basic idea is to think of the phase difference between two paths in the multiway system as corresponding to the ratio of branchlike- to spacelike-separated events along those paths (or, strictly speaking, to twice the ArcTan of that ratio).