It seems like there must be some form of rate limiting in order to
slow down the search through such a limited set of possibilities.
There is. Due to the nature of AugPAKE an attacker can only try a single password per connection attempt with the server, meaning offline attacks against the handshake transcript are not possible. Thus if the connection-rate is limited, the search speed is limited accordingly as well, protecting even weak passwords, if something like 10 attempts per second and further penalties for bursts are implemented.
The fact that you can't guess anything from a passive view of the transcript is documented (and proven) in section 3.2.
Section 3.3 in turn talks about what active attacks can do and argues that even an active attacker can do no better than an on-line dictionary attack, which means one password attempt per connection.
Could it improve security to use a key stretching algorithm such as
pbkdf2/bcrypt/scrypt/argon2 on the password, or would that defeat the
purpose/efficiency of the protocol?
It would certainly improve the security of the protocol to use a strong password-based key derivation function (PBKDF) in so far as it hardens the server's password database in the sense that a leak of the database isn't directly equal to "many, easy-to-break real-life password hashes". However this would also impose high loads on the clients of such a connection, which may be unfavourable, especially as there's no one-size-fits-all for password hashing given how different desktop computers and smartphones are, where the former needs maybe 100ms for something the latter needs 3s. This is very likely the reason why there's no such strong PBKDF in place here, as the designers decided that speed is more important than "security in case of database leaks".
This is also part of the security discussion of the document (section 3.5) which says that a protocol is secure against server compromise as long an attacker can do no better than running off-line dictionary attacks on the database.
What prevents an attacker from brute forcing the weakest link in the
The weakest link in the chain is the password database (which is secured using standard access control) or by the nature of the protocol, making guesses really slow and controllable.