I haven't found a way to do it in Notes, but in TextEdit it's possible with Applescript. It will change color every time a blank line is encountered.
If you want to have the colored text in Notes you can copy it from TextEdit and "Paste and keep style" in Notes.
I tried many ways to randomize the colors, it doesn't always produce a favorable result, if the set doesn't suit you just run the script another time. Random is not always so random in Applescript.
tell application "TextEdit"
activate
tell front document
set Red to random number from 0 to 65535
set Green to (Red * 9 + (random number from 0 to 65535)) mod 65535
set Blue to (Green * 11 + (random number from 0 to 65535)) mod (random number from 0 to 65535)
set textColor to {Red, Green, Blue}
repeat with aParagraph in paragraphs
set color of aParagraph to textColor
if character 1 of aParagraph is linefeed then
set Red to (Blue + (random number from 0 to 65535)) mod 65535
set Green to (Red * 3 + (random number from 0 to 65535)) mod 65535
set Blue to (Green * 5 + (random number from 0 to 65535)) mod (random number from 0 to 65535)
set textColor to {Red, Green, Blue}
end if
end repeat
end tell
end tell
Sample:
