Your Galaxy S4 must have Android 4.3 update before it'll link to the Galaxy Gear. Android 4.3 is only on the Note 3 and Note 10.1 (2014 edition) right now. This is the case with all carriers, not just Verizon.
Verizon never gives a date ahead of time for a phone update - plus they have the track record of being slower than all the other carriers.
Did you buy this Galaxy Gear in a Verizon Store? I would have hoped someone would mention this to you - nobody wants to spend $300 on something that won't work until a future point in time. 