500 Hz PWM? That is slow. That would be fine. Are you send shiftOut( ) or SPI signals too?
One way to solve the problem for longer distances is put a microprocessor on the other end, and hook both up with RS485. Then on the first processor, it just sends down requests (turn on PWM to this frequency, turn it off, turn on led, etc.).I would use a microprocessor with serial support on each end, and not something like ATtiny85's. That way, the RS485 handles error correction, etc. and you are not sending PWM signals down the line continuously. You don't necessarily want an Arduino development system on each end.
Another thought if you were willing to live with i2c distances (something like 2m, but I don't actually recall), Adafruit sells a 16 channel i2c PWM controller that would off-load doing the PWM processing: https://www.adafruit.com/products/815