Are Feistel ciphers subject to the birthday bound?
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.