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
Star grounds for most things, and especially for power supplies, is bad. It is much better to just have a giant solid ground plane across the entire PCB, and have short & thick traces from your components directly to the plane.
While you're at it, you should have a solid plane for your +12v rail. Although I'm less sure about this, because it depends a lot of stuff you didn't put in your schematic.
The reason why star grounds are generally bad is because it provides the opportunity to have ground voltage differences in different areas of the PCB's due to current flow in the ground traces. Very careful PCB routing with really wide traces can prevent that, but just using a solid plane will reduce the ground inductance/resistance enough that for most applications the need for a star ground (or isolated ground) just goes away.
Update:
If for some reason you can't have a solid ground plane, then approximate one as best you can.
Do it like this: First, identify your high-current paths. This is normally your Vin, Vout, any FET's and Diodes used as the switching elements, inductors, the caps on Vin and Vout, and the GND that connects these parts. Route these traces first. Make them as short and fat as possible. What you're trying to do is give that path a very low impedance/resistance and also reduce the loop areas. After that, route everything else. When routing the GND, try to approximate a gnd plane. Sure there will be lots of holes, but you'll get reasonably close. And since you routed all of your high-current GND traces already, the really critical stuff has already been done.
It is most important to reduce the noise on the high current paths, even if that means more noise on the grounds. This is a switching regulator after all, some noise is to be expected. By dealing with the high current paths first, you are going to have a higher net noise reduction than anything with a star ground.
Unfortunately, if you can't have solid power/ground planes then everything is going to be a compromise. It'll never be perfect, and it'll never be "right". You'll have to settle for "good enough". On the plus side, I'm sure you can end up with something that works for you.
Best Answer
The decoupling capacitor must be connected as close as possible to the supply pins of the device in order to minimize inductance in the high-frequency loop. This is true regardless of what grounding scheme is in use.