Are CNNs indeed translation invariant?
Short answer - No, CNNs are not really translation invariant.

I specifically mean the style of image classification network in the paper you mentioned (i.e., (input) > (conv layer) > ...  > (conv layer) > (fully conn layer) ... > (fully conn layer) > (output)).

This is partly because of the difference between translation invariance and translation equivariance (an important distinction, imo). See this question and the answers

Why

The last few layers in the network are fully connected (FC).  FC layers are definitely not translation invariant (they don't give consideration to the spatial relationship between the inputs).  But, the whole network could still be translation invariant if everything before the first FC layer is translation invariant.

We have convolution layers before the FC layers, but convolution layers are translation equivariant, not translation invariant (see below, it'll make sense).  Therefore the whole network is not (really) translation invariant.

Adding pooling layers after convolution makes the network invariant to small translation motions.

Convolution operations are translation equivariant

Translation equivariance of a function means that it's output for a translated version of the input is a translated version of the output.

if $$f(x(i)) = y(i)$$
then $$f(x(i-t)) = y(i-t)$$
where $i$ is the spatial index

Compare to translation invariance

Translation invariance means that the output of a translated version of the intput, is exactly the same as the output for the original input.

if $$f(x(i)) = y(i)$$
then $$f(x(i-t)) = y(i)$$
where $i$ is the spatial index