Integrating nanoscale electromechanical transducers and nanophotonic devices potentially can enable acousto-optic devices to reach unprecedented high frequencies and modulation efficiency. Here, we demonstrate acousto-optic modulation of a photonic crystal nanocavity using Lamb waves with frequency up to 19 GHz, reaching the microwave K band. The devices are fabricated in suspended aluminum nitride membrane. Excitation of acoustic waves is achieved with interdigital transducers with period as small as 300 nm. Confining both acoustic wave and optical wave within the thickness of the membrane leads to improved acousto-optic modulation efficiency in these devices than that obtained in previous surface acoustic wave devices. Our system demonstrates a scalable optomechanical platform where strong acousto-optic coupling between cavity-confined photons and high frequency traveling phonons can be explored.