How do I know if my microcontroller clock frequency is fast enough?
In case it is difficult or impossible to estimate the required frequency theoretically (based on calculations and the knowledge of the microarchitecture) or based on experience (similar code on similar machine), the empirical approach can be taken. A common technique to write an embedded real time application is by having the main loop to be fixed time long. Than your main loop will look something like that:

while (true)
{
    doStuff();
    waitSync();
} 


waitSync here is driven by some kind of timer interrupt. By adding an indicator like GPIO pin output like this:

while (true)
{
    gpioOn();
    doStuff();
    gpioOff();
    waitSync();
} 


and placing a scope probe on that GPIO you will  get a nice pulse train, whose duty cycle will indicate the percentage of the CPU time, when it is actually "doing stuff".