Google says there are packages, therefore it must be true.

Just to move leds, osc may be a little overspecified - try midi

Yes, you can do it, there are OSC libraries available for Arduino (check out Recotana's) but for LED control I'd only bother if you want to use your Arduino on a network. If you are just USB connected then probably best use serial.

If you have an ethernet connection between your arduino and your computer, you don't have to use OSC, you can simply send datas over UDP (with mxj net.udp.send), as you would do over a serial connection.

If you did use OSC, you could control your LED's from a tablet or anything else running OSC compatible software, but hey, that's getting away from Max a bit and its probably simpler to just do what Patrick said.

Siska Adams UDP object also allows you to send serial data over UDP (the native Max udpsend object insists on an OSC format). Not sure if there is any speed difference?