There is no need to re-download it. Deleting the shortcut does not imply the fact that the application will also be deleted. You can find all the Kies products in : C:\Program Files\Samsung\Kies or C:\Program Files (x86)\Samsung\Kies if you're using a 64-bit operating system. Also, Kies Air service discovery is installed with the Samsung Kies installation.
Make sure that when the installation is nearly its finish state to check for Kies Air.