Cost of computational representation in PAC-learning definition
I found a satisfactory answer in chapter 1.2.2 of "An Introduction to Computational Learning Theory" by Michael J. Kearns and Umesh V. Vazirani.

Basically they consider for each natural number $n$ a concept class $\mathcal{C}_n$ over $\mathcal{X}_n$ (where $\mathcal{X}_n$ is either $\{0,1\}^n$ or $\mathbb{R}^n$), and let $\mathcal{C} = \bigcup_{n \geq 1} \mathcal{C}_n$ and $\mathcal{X} = \bigcup_{n \geq 1} \mathcal{X}_n$. So it is indeed necessary to look at all concept classes at once in order to make sense of the parameters $n$ and $\mathrm{size}(c)$ in the polynomial that gives a lower bound of the required sample size.

In the cases $\mathcal{X}_n = \{0,1\}^n$ or $\mathbb{R}^n$ it is also clear that the cost of computational representation is in $\mathcal{O}(n)$.

All this makes sense in any setting that works for arbitrary $n$, e.g. learning axis-aligned rectangles (or $n$-dimensional boxes) can (in a natural way) be generalized to $\mathbb{R}^n$ and the universal concept class $U_n$ is obviously another example.