Guidelines to avoid Negative Slack with State Machines

--- Quote Start ---

When you get a negative slack in the route report, how do you systematically debug it?. The route report shows long combinational path in terms of the net names generated in the synthesis, and how would you relate it to your code?

--- Quote End ---

I'm not sure if it is related to your problem, but at least the following expressions are perhaps inferring too much combinational and sequential logic due to the non covered status on if expressions, particularly because you have a lot of states:

STATE1:
    begin
        if(condition2)
            nextstate = STATE2;
        else 
            if(condition3)
                    nextstate = STATEX;
            else
                    nextstate = IDLE;
    end

I would recommend you start thinking about use the when-case statement instead.