Does the capacitor dielectric experience heating due to rapid charge/discharge cycles?
Yes, but only to the extent it is not a perfect capacitor.  A perfect capacitor is not capable of dissipating energy, which means it can't be heated by the current thru it since that would represent a loss.

Real capacitors have a spec called equivalent series resistance, or ESR.  That is various physical factors lumped together.  You can for most purposes think of the capcitor as ideal with a series resistor of the ESR value.  A resistor dissipates power proportional to the square of the current thru it.

Real capacitors can get hot with sufficient current and can eventually fail as a result.  Electrolytics are particularly susceptible to this.  Not only is their ESR high relative to other cap technologies, but they are more sensitive to high temperatures.  Some electrolytic capacitors are specifically designed for higher currents, such as the Panasonic FK series.  Look at the FK series datasheet in comparison to other types and you will see the FK can tolerate higher ripple current.  They are also somewhat physically bigger and more expensive than the other types.

Ceramics generally have very low ESR, but it's not zero.  I once got a ceramic disk capacitor so hot it hurt to touch it, and that was at only 1 MHz.  (Maybe the 10s of volts from a RF transmitter I was putting accross it had something to do with it :-) )

Dielectrics store energy in the D field by sloshing electrons around at least a little bit.  Some also flip atoms between different energy states.  Any time you move energy around, even at the scale of a few atoms, there is the opportunity to lose some of it as heat.  Some ceramics lose less than others, and ceramics as a whole lose very little, but they all lose some.

Air capacitors don't lose any power in the dielectric since there isn't any (basically vacuum), but unless the leads and plates are superconducting there will be loss there as charges slosh back and forth.