Is there something I am missing in being able to resolve 1Hz from 0 to 10Khz?
Generating a frequency boils down to dividing the processor clock by an integer value. Some examples...
16000000 / 1600 = 10000 Hz (Excellent! A perfect match.)
16000000 / 1601 = 9993.753904 Hz (Uh oh.)
16000000 / 1602 = 9987.515605 Hz
16000000 / 1603 = 9981.285090 Hz
There is no possible way to get 9999 Hz out of a ATmega32u4 running at 16000000 Hz.
My second option of using a PWM to output a voltage was even less successful as the standard analogwrite function will only take 0-255, I would again need at least a resolution to handle 0-10000. The Atmega32u4 has PWM outputs that can be setup for 16-bit, its just the case of figuring out how to do it.
Make an attempt to get it working, post your Sketch, and I suspect someone will provide help.