Key derivation on Arduino
There aren't many KDFs that will be faster on an AVR than PBKDF2. In your case, it's likely that the only thing you can do is find a hash which can be implemented efficiently on an ATmega2560, and implement it with as many optimizations as possible. A highly-optimized implementation of a hash algorithm is likely to improve speed significantly. That's really all you can do: Find/write a very fast AVR implementation.

If you find that PBKDF2-HMAC isn't giving you optimal performance, you could try to use a similar KDF such as S2K of the OpenPGP standard. It works by concatenating the password and salt and feeding that data into some chosen hash function. It is fed, repeating, until the configured number of bytes have been processed. See RFC 4880 § 3.7.1.3 for the specifications. It does not require any optimizations beyond optimizing the hash itself, unlike PBKDF2-HMAC. Benchmark it and see if it's good for you.