Does it make sense to recompute Parks-Mccellan on a per sample basis?
No, the Parks-McClellan algorithm, which is based on the Remez exchange algorithm, is a computationally quite expensive iterative method that is most commonly used for off-line filter designs. It is not at all well-suited for real-time applications, let alone for re-designing a filter each sample interval.

Depending on your application, you might be looking for an adaptive filter based on the LMS (least mean squares) algorithm.

Another approach, again dependent on the application, is to use an appropriate parametrization of the filter, where the parameters could be the gain, center frequency, Q factor, etc. This is easily possible with second order IIR filters.