ATMega328P How many interrupts per second can it handle?

At those speeds it should not be a problem, but for more critical timing you might want to look into assembly language. You would have to do all the work, but the cosde can be much faster because you only have to save registers you are really using so the save and restore code can be much shorter. Depending on what else oyu are doing, you might be able to keep each routine in its own set of registers...