Is primality essential in Varshamov's bound?

The analogue of the Varshamov inequality need not hold for instance for $\lvert\Sigma\rvert=q=6$: For $n=4$ and $d=3$ it would give a code $C\subseteq\Sigma^4$ with $d(C)\ge3$ and $\lvert C\rvert=36$. But such a code gives a pair of orthogonal Latin squares of order $6$, which is known not to exist (by Tarry's negative answer to Euler's thirty-six officers problem).

(The construction of the orthogonal pair $A,B$ is as follows: Since $d(C)\ge3$, the map $C\to\Sigma^2$, $(i,j,a,b)\mapsto(i,j)$ is bijective. For $(i,j,a,b)\in C$ let $A$ and $B$ have entry $a$ and $b$ in the $i$-th row and $j$-th column, respectively.)

Interesting question.

I hope I haven't misunderstood it but the discussion on p. 315 of Handbook of Coding Theory, Vol. 1, by Brouwer seems to imply that a finite field is necessary since it relies on adding a column to the parity check matrix that is not a linear combination of fewer than $d-1$ columns, so the argument is over a vector space. Having a module over a ring might be problematic in terms of applying this argument in general.

See also the short note "Lengthening and the Gilbert-Varshamov bound" by Edel and Bierbrauer here where the techniques used include orthogonal arrays, but those array parameters come from guarantees on dual distances of codes, thus again rely on vector spaces. I don't know whether there are generic orthogonal array constructions that can be substituted in their place.

This is more of a terminological note than an answer.

Historically, Gilbert bound is often called Gilbert-Varshamov bound, adding to the confusion. (Wikipedia articles on it are quite messy too). Gilbert bound does not need linearity of the code (i.e. the collection $C$ of points in $\Sigma^n$ with minimal pairwise Hamming distance $d$), whereas Varshamov's bound does.

IMHO it does not really matter whether $q$ is a prime power; what does matter is whether the minimal distance $d$ code in question is linear or not (i.e. whether $C$ is an affine subspace of $\mathbb{F}_q$ or not). I won't be surprised if a nonlinear code beating Varshamov bound exists. Needless to say, all the codes for $q$ not a prime power are non-linear.

Also there is a closely related asymptotic Gilbert-Varshamov bound. Codes beating the latter are known to exist since the classical work by M.A. Tsfasman, S.G. Vlăduts,Th. Zink and M.A. Tsfasman, where a "layman" exposition (in Russian) of the result it presented. (A translation of the latter is in Problems of Information Transmission, 1982, 18:3, 163–166).

Due to this terminology clash, finding the relevant references is very hard indeed.