Robin2:
I don't know what exactly you are referring to. My 32u4 datasheet has a table 18-12 which shows Baud rates for 16MHz and there is no error at 250k, 500k or 1000k.
Strange, probably mistake on original datasheet on Microchip website. But I believe that you are correct and this is true.
Robin2:
HOWEVER ... the Arduino Leonardo and Micro communicate with the PC over the USB cable at the full USB data rate and the selected baud rate is ignored. (I think you must, nevertheless select a baud rate with Serial.begin() ).
Right, I am stupid 
I was thinking about this problem so much, that I forgot that actual data transfer between MCU and PC is standart USB protocol full speed transfer and decoding as UART is made in driver side of PC... So basically I just need to take care about proper USB shielding no matter of protocol used.
Robin2:
I don't know anything about HID USB - I thought that was just for when you want to pretend that the Arduino is a keyboard or a mouse.
That is not 100% correct. USB HID protocol was actually developed primary for mouse, keyboards, gamepads and some other stuff.
But there also exists USB HID RAW protocol (subclass of HID protocol), It is very similar to mouse or keyboard transfer, but simplier to interface. Using this protocol allow to send any data in very similar way as in UART. But this protocol cal use advanced USB features and downt need drivers (on Windows). I noticed that many small MCU commercila devices actually use this protocol more often than UART emulation.
Robin2:
However my standard baud rate with 16MHz and 8MHz Atmega 328s and Attiny 1634s is 500,000 - and I have never noticed a problem.
500 000 is nice transfer rate. At time of writing, I noticed that HID library for Arduino dont support ARM boards. So HID is probably out of game for now... So I guess that I have to probably try both boards and try 1 000 000 bps. Hope it will also work nicely, if you never had problem with 500 000.
Thanks for your input!