You have three options.
The first is to simply redefine the existing style to have the attributes you want. Second is to define your new style, then delete the old style and when prompted replace it with the new style. Both of these methods will affect all text to which the old style is assigned.
If you want to keep some paragraphs with the old style and change others to the new, you will need to define the new style, then use Find/Change to llok for the old style and change to the new. If there is something common to all the paragraphs that need changing, but that is not present in those that do not get changed you may be able to design your query to find only thos paragraphs. Otherwise it will be a case of going through paragraph by paragraph and chooing either Find Next to leave it alone, or Change and Find to make the change and move to the next paragraph.
Peter, thank you for your answer. I'll try and write back if this helped (I hope that it will save me hours of work).
Also, can I do something like that for tables? I have 2 kinds of table styles that I'll use instead of old styles?
Once more, thank you for fast reply!
I don't do much with tables, but my guess would be that if you can you should redefine the existing styles. As far as I know you cannot search for table styles using Find/Change, and I don't know if deleting one would prompt for a replacement, though it's easy enough to find out -- just try it and see. You can always undo if necessary.