Electronic – Placement of decoupling capacitors

At least for this capacitor you seem to be able to place it on the top layer. If you would place it there at the same coordinates you would shorten the distance between cap and IC pins by at least 80% (you also have to calculate the PCB's thickness). I would definitely try to do so. You can even move it a bit closer. Don't listen to Russell :-) when he says that it doesn't make a difference if you need the via anyway; it's the distance between cap and the \$V_{DD}/V_{SS}\$ pins that counts.
Also, depending on the CPLD's power needs the 10nF may be a little bit small, though this might be more of a problem for FPGAs than CPLDs. Depends both on the number of gates and the clock frequency. Still, when I use a 10nF cap I place a 1\$\mu\$F cap in parallel, with the 10nF the closest to the pins.
Daisy chaining your loads on a single power trace is not a good idea. Instead make the power supply's output a star point and connect your different devices on different traces, each with their own decoupling.

edit
Your third screenshot is definitely the best, decoupling-wise. (I would even let the traces go straight down.) I see no problem with the ground plane, nor with vias connecting to it. Just don't place the via between the cap and the CPLD pins. Distance caps-CPLD should be very short, if possible even shorter! :-)

edit 2
I didn't pay attention to the package first, but your fourth screenshot makes it obvious: your caps' packages are huge. I see Mark made a note about it as well, and I agree with him: switch to a smaller size. 0402 is pretty standard these days, and your PCB assembly shop may do 0201s as well. (AVX has 10nF X7R in 0201 package.) A smaller package will allow you to place the capacitor closer to the IC, yet still leave room for neighboring traces.

Further reading
Choosing MLC Capacitors For Bypass/Decoupling Applications. AVX document
Using Decoupling Capacitors. Cypress document

While not exactly what you're looking for, I have used power-management ICs to accomplish this. For instance, the TPS2113APW. I prefer this specific chip because it allows me to make dual-powered devices that can operate with either a wall-wart or off the USB, automatically preferring wall-power if it is available.

If you don't need dual-powered, you could use something like the MIC2545A

Ultimately, any capacitance "behind" the power-management IC (i.e. hooked up to the IC outputs) isn't "seen" by the USB; the bus only sees the capacitance "in front of" the IC (i.e. hooked up to IC inputs).

You still have to worry about inrush current - the "plus any capacitive effects visible through the regulator" part of the spec - but those ICs also have variable current limiting. Figure out the parallel resistances that you need to have 100 mA limitation and 500 mA limitation (and optionally n mA limitation if you want to limit wall-power), and then use FETs to short out the resistors as needed to enable various limitations.

Through these chips, I have attached PCBs with several hundreds of uF to the USB, and a DMM set to fast current max verified that the inrush during attachment did not exceed 100 mA.