Kindle update now available from Amazon
Amazon have now made a Lion-compatible download available for Kindle for Mac here. Be aware that you may have to delete your current Library and re-download your purchases from the Archive. If you have a lot, you can just do this on an as-need basis or you could just spend the time doing it all in one go straight away.
Note that the update hasn’t appeared in the Apple app store at the time of posting.