Den Schritt mit dem auf 256 Farbe verringern.
Würde ich mit einem anderen Programm machebn als mit Paint.
Paint ist nicht umbedingt der Farbregulierungskünstler ^^"

Versuchs mal mit Photoshop.