From that same document:
In any case the minimal recommended length for K is L bytes (as the hash output length).
So as long as the key is fully randomized, i.e. a cryptographically strong key, the time for brute forcing is at least the same or higher than the time finding a collision. If your key is indeed smaller or not fully randomized, then brute forcing attacks may indeed apply.
If you can find a collision, then you could possibly replace the message. But the hash would still be dependent on the key, so you should see this as a strict lower bound. An attacker would still not break HMAC by only finding a collision (otherwise HMAC with MD5 would be broken by now).
For instance, Wikipedia mentions:
The cryptographic strength of the HMAC depends upon the size of the secret key that is used. The most common attack against HMACs is brute force to uncover the secret key. HMACs are substantially less affected by collisions than their underlying hashing algorithms alone.Therefore, HMAC-MD5 does not suffer from the same weaknesses that have been found in MD5.