Fixing Setup and hold timing violations in FPGA's and ASIC designs
This answer is more geared to an ASIC than an FPGA, but some will still apply.

To address setup time violations, you can:


Use larger/stronger cells to drive paths with high capacitance, which can reduce the time needed to transition on sluggish net.
Adjust the skew of the clock to the start or endpoint of the path which is violating. (time borrowing).
Move gates around to make the total distance between different cells in the violating path smaller (less capacitance to drive = faster transitions)
Insert retiming flops on the path, if the design will allow for it (try to do an operation in two clock cycles instead of one)
Reduce the overall clock frequency.


For hold time violations:


Skew the clock to the start/endpoint (reverse of how to fix setup) to make the endpoint clock arrive earlier.
Insert cells along the path to increase the propogation time (insert chains of buffers)
Reduce the drive strength of cells on the path to make the transition time increase.