You can check the old and new values of the Priority field and prevent the users from changing the priority to a lower value.
You can use something like this in your validation rule formula:
AND(
ISCHANGED(Priority),
CASE(Priority,
"P1", 1,
"P2", 2,
"P3", 3,
"P4", 4,
0) <
CASE(PRIORVALUE(Priority),
"P1", 1,
"P2", 2,
"P3", 3,
"P4", 4,
0)
)
This formula will evaluate to true if the Priority field is changed and the new value is lower than the old value, based on the numerical order of the priorities. You can also add a custom error message to inform the users why they cannot change the priority to a lower value.