Why microcontroller takes many clock cycles to start up with PLL clock source?

Deeper interpretation: The PLL is actually producing clock cycles during that whole time. The problem is that until it achieves "lock", the clock cycles may at times be too short to allow the CPU to operate correctly, as the VCO control voltage swings both above and below the target value before settling down.

So what this specification is really telling you is that this is how long it takes before the clock frequency being produced by the PLL is guaranteed to be within the range required by the rest of the chip.

This specification is based not on how fast the VCO itself is running, but rather on the bandwidth of the PLL's internal feedback. There's a tradeoff between fast start-up (wide bandwidth) and low jitter (narrow bandwidth). Some chips actually give you the ability to select different bandwidths for different applications.

You are correct that 1K CK means 1000 clock cycles.

Yes it does take this long as the PLL has to adjust frequency through a wide range until it reaches the correct value by achieving a phase lock. The phase lock process will take much longer than if you bypass the PLL.