We have had troubles updating site icons in SharePoint Online. It might be related to one of the following:

• It occures only on hub sites
• The sites have a custom theme

The error message:

We experienced a problem updating the icon. Please try again in a few minutes.

But what I found is that there are two places where you change the site icon. If the first does not work, try the second one, that was what worked for us: