After many experiments, testing, re-configuration, bashing of head against wall, etc., I found the problem, which I think is bizarre.
When I copied my API Signature credentials from PayPal's sandbox account screen (paypal.com/developer>Dashboard>Accounts, expand the sandbox merchant account, click Profile, select API Credentials tab on the Account Details pop-up) it was adding a couple of spaces at the end of the string, which I was then pasting into the VM PayPal Configuration screen. You can't tell because the entry is masked in the VM form. I only noticed the extra spaces because I tried setting up the PayPal configuration a second time, and on a whim tried pasting the API credentials into Notepad. I played around with that PayPal screen, and the spaces are only added if you select the Signature by dragging from the END of the string, not if you drag from the START of the string. Weird! I was using Firefox 35.0.1 to access that screen, perhaps other browsers would not have added the spaces.
When I stripped out the excess spaces, everything instantly worked. This makes me very happy, but I wish there had been a clearer indication SOMEWHERE that there was a problem with the API credentials. So many hours wasted on this problem!