Is it ok to use a 4.5v 800mA AC adapter for a device when the original adapter is supposed to be 4.5V 500mA - will it damage the device?

Yes. As long as the voltage is the same which it is. The 800mA is the capacity that the transformer can produce safely without going into an overload state. Your original adapter was rated at 500mA which means that what ever device was plugged into it draws less that 500mA. You might notice that the new adapter is slightly physically larger. So you are safe to use the new adapter with the higher rating.