Set.pop() isn't random?

Solution 1:

It's an implementation detail - set is implemented as a HashMap (similar to dict but without a slot for a value), set.pop removes the first entry in the HashMap, and an ints hash value is the same int.

Combined, this means that your set, which is ordered by the hash values, is actually ordered by the entries modulo hashtable size as well; this should be close to natural ordering in your case as you are only inserting numbers from a small range - if you take random numbers from randrange(10**10) instead of randrange(500) you should see a different behaviour. Also, depending on your insertion order, you can get some values out of their original hashing order due to hash collisions.

Solution 2:

When the doc says:

remove and return an arbitrary element from s; raises KeyError if empty

that means the behaviour isn't defined and the implementation can do whatever it's possible. In this case, it seems that the implemented behaviour is to remove the smallest value. That's all.
In fact, set.pop() is based on a HashMap and remove the first element of this (which is the smaller hashcode). In the case of set of ints, it's the smallest int.

On other implementation of Python could return a random value or the first pushed... You can't know.