Include ")" in an exception, to prevent overlaps.
res = StringReplace[myString,
Shortest["(" ~~ (lhs : Except[")"] ...) ~~
city : Except[WhitespaceCharacter] .. ~~
", " ~~
st : Repeated[LetterCharacter, {2}] ~~
sp : Repeated[WhitespaceCharacter, {1}] ~~
zp : Repeated[DigitCharacter, {5}] ~~
rhs___ ~~ ")"] :> city <> ", " <> st <> " " <> zp]
"Some words here, then (the quick brown fox) Los Angeles, CA 90071, and followed by Chicago, IL 60604"
myNewString === res
True