Can I apply multiple Paragraph Styles at the same time ?

You can't apply multiple paragraph styles at the same time: imagine that one of this paragraph style is setup with a justified text and another one with a left aligned text; how would it be possible.

GREP styles are character styles, automatically applied over a paragraph style.

I suspect you're translating "From" and "Next" from another language, right? In English ID interface these are, I'm guessing "Based On" and "Next Style." They're unrelated; Based On is for one style that is based on a parent style.  Next Style is totally separate, that is for when you want to select a large number of paragraphs and then apply Style A to the first, then style B to the second, and so on. Neither one is going to be useful in your attempt to apply two Paragraph Styles to a single paragraph. At no time can you have two Paragraph Styles applied to a single paragraph. 

If you need multiple variants of styled text in a single paragraph, you can apply GREP Styles that apply Character Styles (which you obviously already know), as well as Line Styles and Nested Styles (which, like GREP Styles, apply Character Styles according to a set of rules). You can also just select some text and apply a Character Style to it. That's the main way to have multiple styles within a single paragraph.

So, there's lots of tools for styling text in InDesign. I think that m1b is correct in asking you to make an example file. These tools can be pretty deep, and there is likely a way to get the styling you want with a fairly small number of clicks, and a fairly small number of styles. I mean, I have never yet personally encountered a numerical limit on the number of GREP styles I can apply, and I'm kind of a GREP Style abuser:) , so it is likely that you're overusing the GREP Style tool a little. 

Hi @Nemesis666first, can you make an example file showing what you want to do? I don't think you can apply 2 paragraph styles to the same text in a normal case, but there may be ways around it. Perhaps a script can apply multiple styles' properties to some text, but it won't be a paragraph style per se.

- Mark