Current processing time for citizenship certificates is 5 months (meaning that 80% of all applications were processed in that time). You may get your updated certificate much sooner, but it could take longer.
Note that the name change itself will also take time. In Ontario it takes 6-8 weeks to receive the name change certificate. An updated driver's licence (4 to 6 weeks) and health card (4 to 6 weeks) will also take some time to arrive. Legally (in Ontario) you must request the new licence within 6 days of the moment you receive the name change certificate, so you cannot request the name change and then wait until after your trip is over to update your documents.
It seems unlikely you'll have enough time to get all documents sorted before you leave for Europe, and almost impossible to get a Canadian passport with your new name in that time, so you'll likely have to keep your current name until you're back from your trip.