What constructions for data authentication are subject to the birthday paradox? $H(m\mathbin\Vert k)$ as an authentication algorithm, where $H: \{0, 1\}^* \rightarrow \{0, 1\}^{n}$, has at most a strength equivalent to $\frac{n}{2}$ bits. $H((k^\prime \oplus \mathrm{opad})\mathbin\Vert H((k^\prime \oplus \mathrm{ipad})\mathbin\Vert m))$, the definition of HMAC, has an upper strength of $n$. The security of block cipher modes and block ciphers providing authentication is less clear to me. What parts of a MAC algorithm construction determine if it has a strength of $n$ bits as opposed to half that number?
It turns out that the birthday paradox figures into both the suffix-MAC $H(m \mathbin\Vert k)$ and the HMAC $H((k \oplus \mathrm{opad}) \mathbin\Vert H((k \oplus \mathrm{ipad}) \mathbin\Vert m))$, but in different ways.  And, curiously, there is no theoretical formalism in the field of ‘provable security’ for the way that it figures into suffix-MAC, which is the one that, as you observed, is practically relevant.

The quick summary is that, for a $b$-bit hash function $H$, when $k$ is unknown to an attacker, for suffix-MAC $H(m \mathbin\Vert k)$, the attacker can spend $2^{b/2}$ work offline to find messages $m_a \ne m_b$ that collide under $H$, whereas for HMAC, the attacker must interact online with your system for $2^{b/2}$ messages before they're expected to stumble upon messages $m_a \ne m_b$ that collide under $\operatorname{HMAC-}\!H_k$.

Because $2^{b/2}$ offline work is sometimes feasible, e.g. if $b = 128$ as in MD5 (which also has nongeneric collision attacks that reduce the work to something negligible), whereas $2^{b/2}$ online interactions with a single application is nearly unthinkable, when summarizing MAC security we usually paper it over and say that suffix-MAC has $b/2$ bits of security while HMAC has $b$ bits of security—but you'll find the gory details in papers analyzing the ‘provable security’ of any MAC.

In a little more detail:


The suffix-MAC construction $H(m \mathbin\Vert k)$ for an iterated hash function $H$, i.e. roughly where $H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = f(\cdots(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1})$, is vulnerable to collisions in $f$: if you can find initial message blocks $m_a \ne m_b$ such that $f(\mathit{IV}, m_a) = f(\mathit{IV}, m_b) = h$, then the messages $m_a$ and $m_b$ always have the same authenticator $$H(m_a \mathbin\Vert k) = f(f(\mathit{IV}, m_a), k) = f(h, k) = f(f(\mathit{IV}, m_b), k) = H(m_b \mathbin\Vert k),$$ as do any pairs of messages that start with $m_a$ or $m_b$ and share a common prefix, $m_a \mathbin\Vert m'$ and $m_b \mathbin\Vert m'$.

An adversary who knows $f$ and $\mathit{IV}$—which are a public function and constant, respectively, in cases like SHA-256—can work offline to try to find such a collision.  Once they've found one, and they will know when they've found one because they can just test it, they may be able to break your application immediately with probability 1 and no prior interaction.

This is practically relevant: cryptosystems based on MD5 and SHA-1 were broken in practice by finding such collisions, and MD5 was even exploited to forge HTTPS certificates in a widely publicized incident of international industrial sabotage by the United States and Israel against Iran (although with RSASSA-PSS signatures, rather than with symmetric authenticators).

What's curious is that there's no theoretical formalism in the field of provable security about this.  Every fixed compression function like SHA-256 has collisions.  We just don't know any yet.  We can't say anything formal about an attacker's success probability after a certain amount of work for attacks on these constructions, because there is nothing randomized about them.  Either the attacker knows a collision (and one certainly exists) or they don't, and while we can informally conjecture about their expertise in cryptanalysis, no formalism in cryptography helps with quantifying probabilities about that knowledge.
$\operatorname{HMAC-}\!H_k$ is vulnerable to an internal collision in $H((k \oplus \mathrm{ipad}) \mathbin\Vert m)$: for every $k$, there are guaranteed to be many pairs of messages $m_a \ne m_b$ such that $$H((k \oplus \mathrm{ipad}) \mathbin\Vert m_a) = H((k \oplus \mathrm{ipad}) \mathbin\Vert m_b).$$  In that case, the two messages share a common authentication tag under the key $k$, and so if the sender provides an authentication tag for $m_a$, the attacker can replace the message by $m_b$ and leave the tag intact, and the receiver will be none the wiser.  (A collision may also happen in the outer $H$, of course.)

But the attacker can't try offline to test whether $m_a$ and $m_b$ collide under $\operatorname{HMAC-}\!H_k$, because they don't know $k$, in the formalism of provable security.  So, the attacker's best strategy (in the cases where we do have security reductions) is just to try substituting messages without changing their authentication tags, and the expected number of attempts at forgery before a collision will be about $2^{b/2}$.

The same applies to other constructions, like CMAC, and this is why, if you look closely at the security reductions for many of these constructions, you will find references to the birthday bound, and forgery probabilities in terms of numbers of queries $q$ as long as $q \lll 2^{b/2}$.  A notable exception to this is polynomial evaluation one-time MACs, which work differently, but that will have to be a bedtime story for another night.