[pi_formance]

Thanks kovidgoyal!

I found a way for covers to show up on Kindle for Android and on the Kindle Mac application:
-) Convert epub to mobi (Enable sharing.. un-ticked)
-) Edit the exported mobi file with a Java tool I found somewhere here on the forum - MobiMetaEditorV0.16) - Modify the EXTH record 113 to ensure it is set to the ASIN as per Amazon.com

Now if you open the mobi file with Kindle Mac or send it to your Android using the 'Send to Kindle' app, you'll have the cover showing.
Using this way, you don't have to set the 'Enable sharing' option. The problem remains that the book shows up under 'Personal documents' on my Paperwhite when I send the mobi file to the device using the 'Send to Kindle' app. However, I tried opening one of the mobi files that I sent to my Kindle, went to page 10, synced, opened the same book on my Android phone and it remembered that I was on page 10.

So, I guess I found a workaround to have covers in both Kindle for Android and Kindle Mac which allows syncing of last reads. The only problem is that the books show up as 'Personal' on my Paperwhite.
I tried copying mobi files using a USB cable and Calibre -> If I do that, they are NOT listed as 'Pesonal'. However, they are obviously not stored in the Amazon cloud which means I can't sync my reading status across different devices.