The max7219 data sheet recommends a 0.1uF and a 10uF cap for each chip.
Also I see some LEDs without series resistors in your schematic. Not the ones connected to the max chips, they would not be needed. But several others.
The ATmega internal 8MHz Vs external 16MHz question is not relavent, you can use either. The ATmega communicates with the max chips over the SPI bus, which is a "synchronous" bus, meaning it has a separate clock line. That means that a wide range of clock speeds can be used and minor variations in the clock timing don't matter. Contrast that with "asynchronous" busses such as Serial. With asynchronous busses there is no separate clock line, so data timing is much more critical and sometimes errors can occur if an accurate crystal is not used by both the sending and receiving circuits.