As the result of co-operation with @BitLord69, we experimented with patching multiple records using the following syntax:
Patch(Data source, Table of record primary IDs, Table of change records)
Where the second and third parameter have the same number of rows.
Well, performance is awful. It seems that in any case PowerApps is still patching one record at a time, since the gallery showing 'Data source' was flickering and updating as more and more records were updated.
Suggest updating the connector to patch all the records in one server call, performance would be much improved.