In 1982 and again in 2000 I cycled on the Rail Trail, which runs in a northeasterly (or southwesterly) direction near the elbow of the Cape. It's paved, though the pavement in some spots is lumpy because of tree roots pushing up. Regardless, I enjoyed it both times. It keeps you off the roads (with an intersection now and then), and goes through wooded areas and past cranberry beds. If you are travelling with kids, you won't be in a hurry, so just slow down when you get to the bumps.
There is another paved bicycle trail along the canal that separates the Cape from the mainland. I believe that the trail is on both sides, but I only cycled on the east side.
Have fun, and make reservations early!