Electronic – General tips for 4 layer boards

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

You will hate yourself if you do stack up number two ;) Maybe that's harsh but it's a going to be a PITA reworking a board with all internal signals. Don't be afraid of vias either.

Let's address some of your questions:

1.Signal layers are adjacent to ground planes.

Stop thinking about ground planes, and think more about reference planes. A signal running over a reference plane, whose voltage happens to be at VCC will still return over that reference plane. So the argument that somehow having your signal run over GND and not VCC is better is basically invalid.

2.Signal layers are tightly coupled (close) to their adjacent planes.

See number one I think the misunderstanding about only GND planes offering a return path leads to this misconception. What you want to do is keep your signals close to their reference planes, and at a constant correct impedance...

3.The ground planes can act as shields for the inner signal layers. (I think this requires stitching ??)

Yeah you could try to make a cage like this I guess, for your board you'll get better results keeping your trace to plane height as low as possible.

4.Multiple ground planes lower the ground (reference plane) impedance of the board and reduce the common-mode radiation. (don't really understand this one)

I think you've taken this to mean the more gnd planes I have the better, which is not really the case. This sounds like a broken rule of thumb to me.

My recommendation for your board based only on what you've told me is to do the following:

Signal Layer
(thin maybe 4-5mil FR4)
GND
(main FR-4 thickness, maybe 52 mil more or less depending on your final thickness)
VCC
(thin maybe 4-5mil FR4)
Signal Layer

Make sure you decouple properly.

Then if you really want to get into this go to amazon and buy either Dr Johnson's Highspeed digital design a handbook of black magic, or maybe Eric Bogatin's Signal and Power integrity Simplified. Read it love, live it :) Their websites have great information as well.

Good Luck!