Bonjour Améline,
Oui, vous pouvez commencer les démarches maintenant si vous souhaitez. Prendre de l'avance c'est même plutôt mieux dans le cas ou la demande serait retardée pour x ou y raisons.
Vous pouvez vous rendre sur le territoire dès que vous obtenez votre lettre d'introduction. Par contre, vous devez quitter le Canada à la fin de validité de votre permis de travail ou alors demander un autre permis pour pouvoir rester. Ça peut être une fiche visiteur, si vous souhaitez faire du tourisme par exemple.
Pour les congés c'est à voir avec votre employeur directement mais oui vous aurez sans doute droit à des congés en effet. Et oui, vous avez le droit de sortir de la région pendant la durée de votre permis de travail. Vous pouvez même sortir du Canada.