Turning a frequency locked loop into a phase locked loop
Virtually every MCU ever made includes at least one timer/counter module, so it's kind of silly to use an external counter chain.

Just connect the VCXO output to the input of the timer module (or better yet, use the VCXO as the main MCU clock), and program it to generate your 5 kHz output.

In the firmware, you sample the value of the counter every time you get an intterupt from the GPS reference pulse. If the counter has a low value (assuming it's counting up, not down), it means it's running too fast and you need to slow it down. If it has a high value (i.e., near 2000), it means it's running too slow and needs to be speeded up. Adjust the DAC output accordingly.

Eventually, the rollover events of the counter will be synchronized with the GPS reference pulses.