PairCases_on does not work on non variables

[ordinarymath]

while Cases_on works on terms like evaluate (xs,env,s), PairCases_on does not work.