Is it possible to create a PLL purely in digital design, if so how?
This is definitely possible. It is called an all digital PLL. Instead of a VCO, you use a numerically controlled oscillator, or NCO. An NCO is basically just a counter, called a phase accumulator, that you add some value to on each clock cycle, called the phase step. You then use one or more of the MSBs as the output. You could use the MSB to get a square wave, or you could use several MSBs to get a sawtooth wave or index into a lookup table for a sinewave. Add a digital phase detector and PID controller, and you have an all digital PLL.

The all digital PLL works the same way as a normal one. You don't need to measure the frequency, all you need to do is measure the phase difference and close the loop with a properly tuned PID controller, and the control loop will hunt for and lock on to the correct frequency on its own. You might want to enforce some limits to the NCO adjustment range, though. If you use all "power of two" gains in your PID loop, then you won't even need any multipliers and you can do everything with just adders. 

Now, the downside of all digital PLLs is that you're not going to be able to get the jitter down below one clock period of whatever clock frequency you're running at, for obvious reasons. If your design can tolerate that, then you're good to go. Otherwise you'll need a proper analog PLL.