1. It should work. If you look at the rise and fall times (t_r and t_f) you'll see they are in the nanosecond range. All of the digital ICs are designed to be used in circuits which operate in the megahertz and faster range.
2. The 300mw is a limit - that's the maximum power the chip can safely dissipate without being damaged. At 3V 300mw is 100mA which is a lot of current for a CMOS logic chip.
Power consumption of CMOS logic chips (4000-series, 74HC/HCT) is very, very low - in the micro-watt range.
3. Generally a higher mcd means a brighter and more efficient led which is desirable if you want to conserve power. You also want to choose an LED for its appearance which includes how it's encased - clear vs. diffused. You might just have buy a bunch of different ones and try them out.
You should consider using a micro with a few more IO pins and using charlieplexing:
https://www.reddit.com/r/explainlikeimfive/comments/47097a/eli5_what_is_charlieplexing_and_how_does_it_work/If you have 5 free IO pins you can charlieplex 20 leds.
Update: Realized you might even be able to use the attiny13a. If only one LED will be illuminated at a time, just write a custom routine for each LED which will fade it in and out via charlieplexing.