Are Feistel ciphers subject to the birthday bound? This paper seems to be saying that a balanced Feistel cipher can be broken when an adversary has $2^{0.5 \cdot n}$ pairs of plaintext and cipher text blocks where $n$ is the block size in bits. Is this true?
No. You need to focus on the stated assumptions in the paper.

It is saying that you need 6 or more rounds to get high security against attacks with no more than $2^{n}$ plaintext ciphertext pairs for a classical (balanced) feistel cipher with truly randomly chosen round functions. This is of course an idealized model for a feistel cipher. 

To test your understanding the sentence "In this paper we will show that 5-round random Feistel schemes resist all CPA-2 attacks when m ≪ 2n and that 6-round random Feistel schemes resist all CPCA-2 attacks when m ≪ 2n." is the crucial statement.