What are the implications of a birthday attack on a HMAC? After collecting approximately $2^{n/2}$ message-tag pairs a collision can be observed. So two different messages (m1 and m2) will have the same tag.

This paper states: 


  Then, for any string x, (m1,x) and (m2,x) have the same tags (with high probability in the case of HMAC, and with certainty in the case of CMAC). The attacker can then request for the tag of (m1,x), thereby also obtaining the tag if (m2,x).


Does this mean that it is possible to attach any string x on m1 and the tag of it will be the same as the tag for x attached to m2?

If my assumption is true could this be considered as a length extension attack?
This is like stating that $H(C_1|m_1|x|C_2) = H(C_1|m_2|x|C_2)$ if $H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ for HMAC.

That is probably correct if $H$ is a hash function based on Merkle–Damgård construction (such as SHA-1 and SHA-2) and if $m_1$ and $m_2$ end on block boundaries.

$H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ implies that the state after hashing $C_1$ and $m_1$ is identical to hashing $C_1$ and $m_2$. So adding any data to either one will result in the same hash.

If however $m$ doesn't end on a block boundary then changing the data coming after $m$ will still alter the state after the block has been hashed; it is extremely unlikely that the result will be the same for $m_1$ and $m_2$ (if $m_1$ and $m_2$ differ for the last block of course). If $m_1$ and $m_2$ can be chosen freely then this situation can be avoided.



The situation for CMAC (and CBC-MAC) will be more or less identical. CBC is however explicit while Merkle–Damgård isn't. So this seems indeed more true for CMAC.




  If my assumption is true could this be considered as a length extension attack?


You could call this a length extension attack, it's at least pretty similar to one. With additional data coming after it it's more a kind of insertion attack, but the principles are the same.

Note that this is only applicable to the insertion of $x$, not the rest of the attack.