Prevent testing Head with ReplaceAll

IMHO the simplest solution is to restrict the pattern on the left side of Condition, i.e. change x_ to x_String:

patt = ___ ~~ "a" ~~ ___;

{"good", "bad"} /. x_String /; StringMatchQ[x, patt] -> Sequence[]

(*  {"good"}  *)

You can instead use Replace as indicated in other answers, however:

the optimal levelspec to target atomic elements like Strings is {-1}
The default Heads value False is what prevents List from being pattern matched.

Please understand that Replace does not work the same as ReplaceAll, regardless of levelspec, because it uses a different traversal order. See:

Use Replace instead of ReplaceAll.

ReplaceAll[{"x", "y", "z"}, x_ /; StringMatchQ[x, "x"] -> Nothing]

StringMatchQ::strse: String or list of strings expected at position 1 in StringMatchQ[List,x].

(* {"y", "z"} *)

as in the question. In contrast,

Replace[{"x", "y", "z"}, x_ /; StringMatchQ[x, "x"] -> Nothing, {1}]

yields the same answer but without the error message.

Correction

For nested Lists, it appears necessary to restrict patt to be a String, as noted by Mr.Wizard.

Replace[{"x", "y", "z", {"a", "x", {"b", "x"}}}, 
    x_String /; StringMatchQ[x, "x"] -> Nothing, {1, Infinity}]

(* {"y", "z", {"a", {"b"}}} *)

Solution

You could use Replace (ReplaceAll is effectively the same as using All or {0, Infinity} as levelspec in Replace).

Example

list = {"a", "b", "c"};
patt = "a";
Replace[list, x_ /; StringMatchQ[x, patt] -> Nothing, {1, Infinity}]

(* {"b", "c"} *)

Alternative Solution

In your case, since you are replacing something with Nothing, you could simply use DeleteCases:

DeleteCases[list, patt, All]

(* {"b", "c"} *)

Related