What does it mean the norm symbol applied to a concept?
The only property that the functions $|\cdot|$ and $\|\cdot\|$ need to satisfy is that for every $n$ there is a finite number of $x$'s in the domain such that $|x|=n$ or $\|x\|=n$.
The difference between the two is the domain: $|\cdot|$ is defined on $\mathcal{X}$ while $\|\cdot\|$ is defined on $\mathcal{C}$.

These functions are instantiated on page 1115: for $\mathcal{X} = \Sigma^*$, $|\cdot|$ is the length of the word; and for $\mathcal{C}$ being the set of all DFAs on $\Sigma$, $\|\cdot\|$ is the number of states.