The energy does have to come from somewhere. If you're only cycling 5km in a day the reason you don't notice the difference in food quantity is because the amount of energy used for that small amount of cycling does not really exceed the amount of energy your body uses in a day for everything else. When you're cycling 100km, it's a different story.
It's an interesting question, and in fact the conversion of food to mechanical energy isn't actually very carbon-efficient compared to electricity generation or even gasoline.
Cars are actually very efficient at what they do, it's just that what they do (hauling around a 1000kg metal box) is an inefficient way to transport a human, and that's where the inefficiency comes from.
If you fill up a large car with full occupancy and go on a long road trip, I'd venture to say it's carbon-wise likely to be more efficient than all of the occupants cycling, regardless of diet.