It's not a matter of Nyquist rate. The limited resolution is the problem!
The loop, in C code, will take an unspecified number of instruction cycles. Say it takes 10. Well, if the pulse is high anywhere from 20-29 cycles, that's a 2. And for that matter the looping time is unpredictable, C doesn't guarantee anything in this department. You might compile on a new compiler or even with different options and get a different value for a pulse lasting 27 instruction cycles. There is room for weirdness- if you use a 16-bit "integer" counter, the cycle which rolls over the lower byte counter might take more cycles as it carries. There's NO guarantee of number of instruction cycles in C. ASM code can guarantee it.
Find the loop in the ASM code in MPLAB, count the number of instructions, and count any instruction which modifies the program counter as requiring TWO cycles. A 4MHz xtal is a 1MHz instruction clock, so if your loop did require 10 instruction cycles, that's a total resolution of 50 codes for a 2KHz signal.
Be aware the time for the first loop is different due to the wait-to-go-high, then start-looping.
Interrupts (if used) must be disabled while counting, otherwise a loop which is interrupted will take a wildly different amount of time while the ISR executes.
The Input Capture was made for this. Otherwise, this seemingly simple task really has no elegant solution. I've had an accelerometer that looked great at first because it has these PWM "digital, for easy interfacing with a microcontroller" outputs, then saw there was no good way to interface it with a PIC. The PIC doesn't have 3x Capture inputs, and even the Capture can have a limited resolution creating numeric integrity problems. Basically looking at the options and doing the math, it came up as "wow- this can't be done with a PIC, not even close!"
What device is this which gives its output in PWM format?