This doesn’t have anything to do with WordPress or your user’s passwords.
What it means is that your MySQL server is still using the old-password-hash mechanism, which was changed in MySQL 4.1. The PHP mysqli client is newer and doesn’t support the old password mechanism. Since this causes an error, WordPress falls back to the old mysql client, which does support this but is deprecated (that’s the third error message you see).
In other words, the “password” it is referring to here is not the WordPress password, it’s the password you use to connect WordPress to your database. That username and password in the wp-config.php file, basically.
What you need to do is to change the password for the database itself to the new-hash-version. This is a bit arcane, and if you don’t actually control the MySQL server, you may not have access to do that.
You could ask your host to disable old_passwords, but if it’s a shared database system, they’re likely to be unwilling to do so.
If you do control your server, look into this answer. Note that he got the answer backwards, explaining how to enable old_passwords. You want to do the same basic process, but the other way around, to disable old_passwords and get the longer hash mechanism instead of the shorter one.