PEMDAS is an acronym to help you remember. try different forms of mnemonic devices, like acrostics:
Please Excuse My Dear Aunt Sally;
Pancake Explosion Many Deaths Are Suspected;
Purple Egglants Make Dinner Alot Sickening;
Pink Elephants March, Dance, And Sing;
Pizza ended my donuts addiction Saturday
Well, since parentheses exist precisely to specify the intended order of operations in case the usual default rules don't cut it, it makes sense that they come first
As for exponentation, I'd say that this is a consequence of using superscripts to indicate exponentation, since those (via font size) provide a natural grouping. It'd certainly be very weird if $a^b + c$ meant $a^{(b+c)}$ instead of $(a^b) + c$, since the different font sizes of $b$ and $c$ indicate that they're somehow on different levels.
As MJD pointed out though, this arguments only applies to the exponent. Font size alone doesn't explain why $a + b^c$ means $a + (b^c)$ and not $(a + b)^c$ and the same for $a\cdot b^c$ vs. $a\cdot(b^c)$ respectively $(a\cdot b)^c$. For these, I'd argue that it's also a matter of visual grouping. In both $a\cdot b^c$ and $a + b^c$, the exponent is written extremely close to the $b$, without a symbol which'd separate the two. On the other hand $a$ and $b$ are separated by either a $+$ or a $\cdot$. Now, for multiplication the dot may be omitted, but it doesn't have to be omitted, i.e. since $ab$ and $a\cdot b$ are equivalent, one naturally wants $ab^c$ and $a\cdot b^c$ to be equivalent too.
For multiplication, division, addition subtraction, I always felt that the choice is somewhat arbitrary. Having said that, one reason that does speak in favour of having multiplication take precedence over addition is that one is allowed to leave out the dot and simply write $ab$ instead of $a\cdot b$. Since this isn't allowed for addition, in a lot of cases the terms which are multiplied will be closer together than those which are added, so most people will probably recognize them as "belonging together".
You may then ask "how come we're allowed to leave out the dot, but not the plus sign". This, I believe is a leftover from times when equations where stated in natural language. In most langues, you say something like "three apples" to indicate, well, three apples. In other words, you simply prefix a thing by a number to indicate multiple instances of that thing. This property of natural languages is mimicked in equations by allowing one to write $3x$ with the understanding that it means "3 of whatever $x$ is".
Best Answer
There is no strong convention for these notations.
In most cases the $C$ and $P$ notations are self-delimiting, because the arguments are typeset as subscripts or superscripts. They can be written as ${}_nC_r$ or ${}^nC_r$ or $C^n_r$, where in each case it is unambiguous that the argument expression is whatever is written in smaller type -- or as $C(n,r)$ where the parentheses and comma make the structure explicit.
There are a few cases where ambiguity does arise, such that if you write the functions as ${}_nC_r$ and want to multiply two of them. In that case it is strongly advisable to use parentheses to disambiguate rather than try to rely on a convention: $({}_aC_b)({}_dC_e)$.
In any case, in more complex situations it is often preferred to use binomial-coefficient notation $\binom nr$ instead of ${}_nC_r$, and that is completely self-delimiting. The counts that are written ${}_nP_r$ in some elementary combinatorics texts appear to be rare enough in advanced material that it is generally feasible to write $\frac{n!}{(n-r)!}$ for them.