Yes, your permutation automata concept can simulate Turing machines.
You describe an update procedure $\tau$ that operates on a given permutation of $\mathbb{Z}$, let us imagine the permutation written out in a line, by local rearrangements: the new value at position $n$ is determined by the previous values in the size $|S|$ neighborhood of $n$. One "computes" with such an update procedure by starting from an input configuration that is regular in some way and then iteratively applying the update procedure until some halting feature is observed.
Such a kind of update procedure can encode the operation of a Turing machine and therefore is Turing complete (actually stronger than this, as I explain below). One way to do this would be as follows. Fix a given Turing machine $p$ with fewer than $k$ states for some large finite $k$. Divide the integers into finite blocks of size $k$; these will code the Turing machine cells of the computation of $p$ that we shall simulate. We shall only use permutations that operate on the intervals $I_n=[nk,(n+1)k)$, that is, they only move numbers around inside the blocks of the multiples of $k$. To mark the beginning of such a block $I_n$, we shall place $nk$ in the first position of $I_n$, and our update procedure will not move it. (This enables the update procedure to know where the blocks begin and end.) The next two positions in the block will hold the values $nk+1$ and $nk+2$, either in this order or reversed, in order to indicate the $0/1$ value of the cell that is being simulated. The remaining positions will hold the remaining values from $nk+3$ up to $(n+1)k$ arranged in such a way so as to indicate whether the Turing machine head is present on that cell and if so, what the state is. For example, if one of the values is out of order, then might indicate the presence of the head and the state. The point now is that the update procedure $\tau$ that would carry out the simulation of the program $p$ on these configurations is determined by looking only at the current block and the two adjacent blocks, to see if the head is coming in from the right or the left, and so it fits into your automata concept. Thus, we have a completely local update procedure in the manner you have described, and so your concept can simulate Turing machines.
But actually, your concept is far stronger than Turing machines. The reason is that your function $\mu$ is infinitary in nature, and not all such functions $\mu$ can be simulated by Turing machines. For example, there are continuum many different functions $\mu$, and one can prove that there will be continuum many different update procedures as a result. Thus, one should think about the situation rather as a oracle computation. The function $\mu$ is capable to simulating not only a Turing machine, but a Turing machine will an oracle tape, filled with information. Specifically, one may consider the update procedure that I describe above, but with the idea that an oracle tape is also simulated.