The standard non-parametric test for paired ordinal data is the Wilcoxon, which is sort of an augmented sign test. I don't know of a formula for power analysis for the Wilcoxon, but you can certainly get power analyses for the sign test (there are various resources listed in my question here: Free or downloadable resources for sample size calculations). Note that (as @Glen_b notes in the comment below), this would assume that there are no ties. If you expect there will be some proportion of ties, the power analysis for the sign test would give you the requisite $N$ excluding the ties, so you would inflate that estimate by multiplying it by the reciprocal of the proportion of untied data you expect to have (e.g., if you thought you might have $20\%$ tied data, and the test required $N=100$, then you'd multiply $100$ by $1/.8$ to get $125$). Unless you need the minimum $N$ to achieve a specified power, that should work for you. For example, when running power calculations for more complicated analyses, we often use a simpler calculation and then say something like 'our $N$ was calculated to achieve a minimum of 80% power on the sign test, because the Wilcoxon can be expected to be at least as powerful as the sign test, our power should meet or excede 80%'.
On the other hand, if you have a strong sense of what the distributions will be like, you can always simulate. Although written in the context of logistic regression, there is a lot of basic information about using simulations for power analyses in my answer here: Simulation of logistic regression power analysis designed experiments.