How to write a for-generate statement to generate multiple instances of this parallel sorting network circuit?
I like a challenge and it took me a few tries but I got it working for W bits wide data and D inputs. (D is a power of two).  I cheated a bit because I am rather more proficient with Verilog. This is the RTL View Xilinx gave me: 



I am not giving away the code if only to prevent this website to become a 'Look: free code!' but I can give some tips:

I started with defining D*(D+1) 8-bit buses. This makes that I can use the same bus name everywhere in my generate.

Connect the first D buses to your inputs, the last D buses to your outputs. 

In the odd stage you pass two buses along which makes the bus indices very nasty. A simple solution is that at the top and bottom of each odd state I rename the bus. For the top bus this is:
assign bus[stage*d+d] = bus[stage*d];
Now you always have D buses per stage an all loops become regular for loops.