how to change all text to black

Easier method:

On the Swatches panel menu, select Add Unnamed Colors.

Then select them all (click on the top added swatch and shift-click on the bottom added swatch).

Delete the swatches.

Replace with Black.

Can we assume that the colors are spot formatting, not Character Styles? (If the lattter, simply delete or change the relevant styles!)

It would be fairly simple to reset all Paragraph Styles to their defined state, and assuming their defined color is Black that would remove both spot and Character Style colors. It would also remove any other spot formatting (and Character Styles for italics, bold, etc. if applied).

A more effective step might be to back up to the source document — I am assuming something like Word — and fix the problem there, where it might be more "accessible" through color swatches you can delete, or in the import process.

A few more details about the colors, where they came from, whether their swatches can be preserved on a re-import, etc. would help if the above doesn't point you in a useful direction.