Slow clk output (Spartan-6)
Does this mean that the clk needs 18.826 to reach all clocked parts?


It actually means, that the maximum delay of the combinational path between two FFs driven by that clock (or back to the same FF) is 18.826 ns. This delay is the sum of the clock-output time of the source FF, the delay of the combinational logic, and the setup-time of the destination FF.


  And can I somehow look up what exactly causes this?


After P&amp;R the ISE toolchain runs the static timing analyzer. In this report, you will find the path which actually causes the high delay. If the report is almost empty, then you must specify a clock constraint with the desired clock frequency in a UCF file, which must be added to your project. An example clock constraint would be:

NET "clk" TNM_NET = "clk_grp";
TIMESPEC "TS_clk_grp" = PERIOD "clk_grp" 100 MHz HIGH 50%



  And how could I possible improve this?


As you already buffered the data-path using FIFOs, take a look at the control path. 

A common problem with a chain of FIFOs is, that the last FIFO can stall the entire pipeline when it is full. Same applies to the first one, when it is empty. If the FIFO control signals are not buffered by FFs, then this typically leads to long signal path going through all FIFOs in between. Thus, a lot of LUT stages and routing delay causes a long critical path.