WordPress 3.8 does not need a plugin for Permalink changes

nope not true. When I click from google it still did not redirect old post to new post

You’re right.

But I tested it by typing in an old URL, and it went to the new one. But perhaps that was before the database had been completely updated? Dunno … But it wasn’t working yesterday.

So I suppose a lot of requests on my site got 404 errors for more than a week.

I just fixed that by simply following Yoasts’s instructions at https://www.sfep.org.uk/pub/faqs/fedit.asp

I used the “Generate Redirect” button, and redirects now work flawlessly.

By contrast, redirect plugins are a bother, slow down the page, and they seem to break.

I think you meant to link to this Yoast post instead of that link above:
https://yoast.com/change-wordpress-permalink-structure/