As I understand, the "over the air sync" is different from iCloud sync (for the contacts). Is it the case?
Is the over the air sync just a sync with my Mac itself? So it is just an cordless version of the iTunes sync?
You are correct: the iCloud sync sends data to and from the iCloud servers, and the Wi-Fi sync sends data to and from your computer running iTunes.