@daulagari said:

But adding only a MAC and nonce (authentication only) means adding payload.
To limit the amount of additional data to be send over, I think adding nonce/sequence number and encryption with a shared key is a better idea.

I think it's important to evaluate how much payload will add MAC, because in case of encryption (at least AES) you'll have to round your encrypted payload size to 16 bytes minimum, as far as I understand, and you'll need to add the very same nonce and some kind of crc into message to add randomness and integrity check.

Considering XXTEA - it seems even slower than AES, according to this: http://www.ei.ruhr-uni-bochum.de/media/crypto/veroeffentlichungen/2011/01/29/lw_speed2007.pdf

@hek
Speed - according this http://forum.arduino.cc/index.php/topic,88890.0.html atmegas are capable of performing AES 128bit encryption in under 1 ms, seems promising at first glance
Message length - I suspect the simplest way is to make them 16 bytes
Protection against replay attacks - I think using nonces and checking message integrity with some kind of crc could do the trick
Key exchange - wouldn't pre-shared key solve this issue?

Also I'm not sure if encryption is really a must for this project. As far as I understand the most important thing is to prevent unauthorised control, and for this kind for things there are lots of MAC algorightms which are much less resource hungry than AES. Any opinions?