Quartus introduces large data path delay difference in two builds

There is no random number in Quartus. Given the same input, it always gives the same output. (But even the smallest change will cause a different result).

Part of the reason you get variation is that the solution space is so large. Look at:

http://www.alterawiki.com/wiki/the_quartus_ii_fitter_and_seed_sweeps

So the two paths have different placement. One goes to a LAB that is both an X and Y hop away(basically diagonal) and hence a row and column hop are both necessary. The second one is placed in the same row and therefore only needs a single short line. The placement and route will be different compile to compile, so it's really not possible to compare a sub-portion of the path, as the fitter is working on the whole path. Also note that you have an adder, so there are multiple signals going into the carry-chain, and may not always be able to put them into the LAB right next to the carry-chain.