The "paradox" is really a contradiction of the axiom of unrestricted comprehension:

    To every condition there corresponds a set of things meeting the condition. 

Unrestricted comprehension allows you to build sets out of whole cloth, and seems reasonable. Of course everything divisible by two is a set, of course every prime number is a set. It's tempting to say that the set is simply defined by a single condition, and if some item fulfills that condition, it gets to be in the set.

Your example would not violate the axiom of unrestricted comprehension. No primes are divisible by 4, so the set of all primes divisible by 4 is the empty set. Russell's paradox does. He chose a condition that depends on the result of creating a set using that condition. "The set of all sets that do not contain themselves" can't contain itself, but it can't not contain itself either -- since either case would imply the opposite must be true.

The result is that unrestricted comprehension gets pared back. Instead of building a set from a condition, all sets must be built from a condition and a pre-existing set. A single infinite set corresponding to the natural numbers is given as an axiom, and all further sets (integers, real numbers, topological spaces, fields, and so on) are built from there.