The EPM3K/7K series are absolutely suitable for synchronous design. I have used them in that way for years with clock rates from 10MHz up to 50MHz.
The noise spikes on the clock edges are not unexpected, as current will be drawn during signal transitions. Unfortunately the spikes will be exaggerated in your design because of the poor quality of your power distribution. Your traces on the two layer board will be highly inductive and are causing this noise to be generated on the power rails. Depending on your LED series resistor values you might also see high current draw (which in an inductive environment causes ringing) from the LED currents.
For reference, my test board designs for the EPM7064S and EPM3064A series PLCC44 parts use a four layer design with full power and ground planes under the device. Local 10uF bulk decoupling. No individual 100nF devices. Using a 50MHz CMOS oscillator and a design which has 60 registers and 64 macrocells as three simultaneous 18b binary counters I see no more than 100mV of noise on the power rail (5V or 3.3V as applicable to the device).
Also, on your BCD to seven segment decoder outputs, they are not synchronous, it is just logic, so expect to see switching noise on the edges as the 4b synchronous counter values propagates thru the logic. They may bounce up and down for 10 to 20ns after each clock edge. That is expected for non registered outputs.
PS: one additional thought ... what type of probing arrangement did you use on your scope to capture the waveforms?
I am guessing it is a probably 10X scope probe and there is a ground lead of 10cm or so in length that you connected to a ground point.
If so, this can add additional ringing on the measured signal due to the probing ground loop (it is inductive) that is not really there.
Ideally you would use a probe with an adjacent 2.5mm or so ground connection clip so there is no long ground loop connection.
Just thought I would ask ...