How do I determine if I can safely substitute potentiometers?
The acceptable range of pot value substitution would depend on the rest of your design: 

In audio applications, volume control pots could, for instance, affect the input impedance (or not) or other performance parameters. If the pot is being used as a simple voltage divider, then you would not want to decrease values too far i.e. increase the current draw across the pot too much compared to design. 

At the same time, increasing the resistance too much would introduce an additional noise source, and may decrease the designed linearity of the divider - such as if the input impedance of whatever is reading that divided voltage, is of comparable magnitude to the pot's resistance. That's like throwing in a third resistance in parallel to one of the arms of the voltage divider, it's no longer a simple voltage divider.

Another parameter especially significant in audio designs is whether the pot is expected to have a linear, log or other more exotic taper (rate of change of resistance with wiper rotation / movement). Substituting one type for another will almost definitely introduce odd behavior.

As a general rule, one would substitute for a quick experiment, but not for a production run, without revalidating the design for the new value. Such substitutions should retain the taper of the original pot. On value range, it is a personal preference: Some would say do not go over twice or below half the design values, perhaps that too is pushing things to the edge. 

Finally, you won't know till you try - and sometimes letting the grey smoke out of your circuit is a good indicator that the substitution was too far beyond acceptable range.

To answer your 500 Ohm for 100 K substitution query: Don't. That's a good candidate for smoke effects.