In principle, it is theoretically possible to calculate the time it takes a machine to run some known algorithm.
It used to be fairly commonplace, but there are apparently very few people who have ever done it -- the sorts of things that used to require isochronous code are now-a-days generally done in other ways.
In practice, it's generally simpler and takes less human effort to write the code and run it on the target machine and measure the time.
According to people on the Internet, some implementations of AES-256 that run directly on the 16 MHz Arduino can encrypt approximately 1 block per millisecond, roughly 32 000 bytes/sec.
(a) (b) (c) (d) (e) (f)
I hear that AES implementations are available on many other 8-bit processors.
AN953 "Data Encryption Routines for the PIC18" describes two AES implementations for a 10 MHz PIC. The "C" implementation decodes 3 400 bytes/sec; the assembly implementation decodes about 14 000 bytes/sec.
(g) (h) (j)
I also hear that many people connect Arduinos to some other devices that does the AES encryption for them, such as some ZigBee and XBee radios with the "Enable AES 128 encryption" command.
Have you heard that Carl is doing AES+CTR+HMAC Encryption and Authentication on an Arduino ?