- if the attacker finds another message m' different from m such that h(m') = h(m) this doesn't guarantee that the prefix of m' is equal to the prefix of m, so with high probability H(k || m' || k) will be very different from H(k || m || k).
Correct: an adversary can't do a collision search offline because the adversary can't even evaluate the function $m \mapsto H(k \mathbin\| m \mathbin\| k)$.
- if the attacker wants to append extra bits to H(k || m || k) and compute another step of Merkle and Damgard algorithm he/she can't because he/she doesn't know the last block (that is the key), he/she only knows message blocks sent during the communication.
Correct: although if given $h = H(k \mathbin\| m \mathbin\| k)$ the adversary could compute $H(k \mathbin\| m \mathbin\| k \mathbin\| m')$ for some suffixes $m'$, that is of no consequence unless by luck $m'$ happens to end with $k$, which is completely improbable.
- if the attacker finds with birthday attack a message m' such that h(m') = h(k || m || k), he/she cannot verify if that authentication tag is correct because he/she doesn't know the key k. So the attacker to find a message m' such that h(m') = h(k || m || k) generates all possible hashes (considering the rule of birthday bound) in order to find the same value of H(k || m || k).
I don't really understand what you're getting at here, because $H(m')$ is not relevant to the authentication system.
All that said: The birthday paradox is nevertheless relevant even if the adversary can't perform an offline collision search!
Suppose you're using a 128-bit hash like MD5, and you learn the authentication tag $H(k \mathbin\| m_i \mathbin\| k)$ for a whopping $2^{64}$ messages $m_1, m_2, \dots, m_{2^{64}}$. Suppose for simplicity that $k$ and the $m_i$ are all at least one full block long—at least 512 bits, for MD5. With high probability, there will be a pair of messages $m_i \ne m_j$ with $H(k \mathbin\| m_i) = H(k \mathbin\| m_j)$, which means not only that $H(k \mathbin\| m_i \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| k)$ but also $$H(k \mathbin\| m_i \mathbin\| m' \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| m' \mathbin\| k)$$ for any common suffix $m'$, enabling forgery of many additional messages! This is why for an iterated hash with an $n$-bit state, you should use it only for ${\lll}2^{n/2}$ messages.
To my knowledge, this was first described by Preneel and van Oorschot in their 1995 MDx-MAC paper. It is a general attack on any hash of this sort with an $n$-bit state; the same idea applies to HMAC too even though HMAC had not yet been invented and Preneel and van Oorschot sensibly chose not to disrupt the natural flow of time by describing how it applies to HMAC.
