ログインに使っているユーザ名が正しいかを確認してみてください。
ログインする前に、[設定] メニューの下にあります。
サンドボックスを使用している場合は、 username@salesforce.com.sandboxのように、ユーザー名にサンドボックス名を追加する必要があります。サンドボックスのセキュリティ トークンも、本番組織のセキュリティ トークンとは異なります。
https://trailhead.salesforce.com/trailblazer-community/feed/0D54S00000A7WABSA3
結果的に、Dataloaderの「Settings」内にURLを指定する部分（Authentication host domain URL for Sandbox）があるのを見落としており、そこを当該のSandboxのログインURLに切り替えたところ無事に接続できました！