VHDL Overmapping and Time Constaint issues in Xilinx-ISE
From the timing report you attached, the critical path has 378 levels of logic in it. I can't emphasize enough how much 378 levels is, from the project I'm working on (video compression), my critical path is only 8 levels deep.

This is part of your problem, not only the propagation delays are enormous from going trough so many LUTs, ISE has a lot of problem routing the design in an efficient way. You need to add registers to pipeline your design, it is much easier to route a pipelined design and you will get faster speed and smaller area. Beside, registers are virtually free in FPGAs.

For instance, your rotLeft entity should have registered inputs and outputs, and it will then easily run at 100MHz, even in a spartan-3E. In my design, I always register my output, and assumes the inputs are registered (since they come from the output of another module).

Another part of your problem is these combinational loops that ISE report. Those are likely to change or even disappear once you redesign to add pipeline registers, but you shouldn't even try a bitstream with these in it.