Electrical – Line impedance in 4 layer PCB

That's the Cypress FX2LP USB microcontroller (I recognize it because I use it myself). If you're using the Hi-Speed USB transceiver, then you should really go with a 4-layer board. Without that ground plane right below the top layer, it will be near impossible to get the 90 ohm differential impedance that you want for the USB D+/D- lines.

http://www.cypress.com/?id=4&rID=34128 flat out states that 4 layers is required. It also states that controlled impedance is required, but in my experience you can usually get away without it, so long as you carefully research your fab's typical stack-up and work out the right width, space, and height.

http://www.cypress.com/?docID=25406 also provides more info on calculating the width, space, and height for the D+ and D- lines.

4-layers isn't that much more expensive; Advanced Circuits has a 66 each deal for 4 layer boards that I use quite often for projects that use that very chip, as opposed to the 33 each deal for 2 layers.

In regards to your actual question...use plenty of bypass caps, as close to the pins as possible. If you split the bottom layer to have VCC and GND, don't have a trace cross the split on the top layer. Keep all high-speed signals on the top layer because the via inductance can kill what fragile signal integrity a 2-layer board has.

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