Should I reinstall Linux when changing the laptop's CPU?
Ubuntu (and generally speaking Linux) don't particularly care what hardware they're running on, and will perform a check on all devices at boot rather than assuming that the same devices are there each time. So long as your CPU is compatible with your chipset, Ubuntu will see it and start using it. Ubuntu 18.04 is also only available in the 64-bit version, so that's not a concern either.
Windows, on the other hand, has licensing to worry about. When you buy a copy of Windows, the idea is that you buy it for a single machine, so Windows tends to more or less "lock" itself to a system's hardware. This doesn't mean that you can't change hardware, but if you do it too frequently (like I've managed to do) it will start to say your key is invalid. If you're in a dual-boot system, this is something to keep in mind.
should I completely reinstall Ubuntu?
No.
Counter-intuitively, changing CPU is one the least meaningful changes in hardware. Usually it doesn't require any changes in software.
That's because your CPU swapping options are extremely limited by socket and chipset. Those limit you to CPUs coming from one or two product generations that are very similar feature-wise. Sure, they may differ in features that matter to you, like number of cores, clock speed and cache size. But those are virtually transparent to the software. The architecture, instructions, registers and all other details that are important to how the software uses CPU remain same. Top execution speed is not something that modern software depends on (the actual execution speed fluctuates all the time due to energy saving anyway).
Even non-open systems, which lock license to the hardware (like Windows) don't consider CPU as "important" hardware. Swapping CPU and RAM are considered standard customer procedures and don't invalidate license.
If the CPU architecture is the same (e.g. 64 bit/amd64) it should work out of the box. 15 years ago, I took a harddisk of one computer to a different one (both 32bit) and it worked out of the box as expected.
The "slower/different start" depends partly on the speed of the CPUs, so if your new CPU is faster/newer/more expensive it should be and boot faster.