Alla fine ho risolto cancellando cache e dati del Google Play Store. Il download e l'aggiornamento di quelle app in attesa sono poi andate.
La cosa strana, però, è che dopo aver fatto appunto la cancellazione di cache e dati, ora quando vado nell'elenco delle app da aggiornare mi dà la vecchia release. Cioè con l'elenco delle app da aggiornare in alto e quelle aggiornate in basso (mentre da qualche mese le dava in schermate diverse).
Google Play Store credo sia aggiornata all'ultima versione, visto che mi dà la 31.2.16-21. Vabbé, mi devo solo riabituare (che poi magari prima o poi mi ritornerà com'era fino a poco fa). L'importante è che sia tornato a funzionare.
Però non è possibile che dimenticandomi di impostare il download su "tutte le reti" avesse fatto tutto 'sto casino...