When hunting for noise and thinking of using filters to address it, it is best to first collect the data and then see what is appropriate.
Since you've wired the sensor to the timer capture input, then you need to make sure that those edges are REALLY clean. Glitches will throw off the timer unit, as it will see those glitches as an edge that triggers the input capture. Therefore, you will want to get an o-scope on that input and make sure that waveform looks nice and clean. Hardware techniques are best here to clean up the signal.
The next step is to simply collect data and analyze it. Ideally, you would run the motor at a constant speed, collect a sample of sensor data, and analyze it. Is it fairly close together? Mean deviation, min's, max's? A graph in Excel would be very revealing at this point. From this data, you would choose your software-side filter (if you even need one).
At this point, who knows what you will find. If you find that it's very consistent but an outlier appears randomly, then a median filter would be best. If the signals vary a bit and you want a smoothed output, then there are any number of averaging, FIR, IIR and so on filters, including some whose math is very easy for use in embedded systems (as in the math is quick and the RAM requirements are low). The exact choices depend on how much weight you want to put on recent values, as opposed to how much weight is placed on historic values. Also note that typical filters will slow your step response.
Since you are running data into a PID, then you want to make sure that your input data doesn't adversely effect the PID. The amount of noise that goes in, or conversely a long response time, will have impacts.
As a veteran of PID programming, it is very handy to have a data stream system off of the target that somehow gets into a spreadsheet on your computer. Knowing the inputs and the states of P, I and D will be tremendously useful for tuning.