Creating a concurrent/parallel ForEachAsync that can fail immediately or wait until enumeration is complete
CancaellationToken is a struct, not a class, so it can never be null. When people don't want to cancel stuff they just pass CancellationToken.None. 
However note that If you change your cts assignment logic to something like parallelOptions.CancellationToken != CancellationToken.None you could hit a NullReferenceException when the cancellation token is None and FailImmediately is false. One simple way to make things work would be to just always assign cts = CancellationTokenSource.CreateLinkedTokenSource(parallelOptions.CancellationToken). Then you won't need the cts nullity check in the loop as well.
Instead of checking for IsCancellationRequested directly, it's a better practice to call cts.Token.ThrowIfCancellationRequested() - that way you will actually mark the task as canceled.
Instead of checking t.IsFaulted, it's a better practice to check if t.Exception != null.
Instead of iterating over t.Exception.InnerExceptions, you should iterate over t.Exception.Flatten().InnerExceptions`.
Creating the ConcurrentBag inside the task like you're doing now is not thread safe. I suggest just creating it upon declaration (instead of assigning null like you do now).
allDone issues:


allDone could be faulted if one of the body methods throw synchronously. 
allDone would have IsCanceled set if cancellation was initiated either by the caller or by the FailImmediately logic
In either case, you won't get to the following line as await allDone would throw.

You don't need else after you throw new AggregateException.
If all you do is re-throw the exceptions at the end of the method, you could just await the Task.WhenAll and get the same behavior for free (without the Console.WriteLine though). To make this work, you'll have to re-throw the exception instead of adding its inner exceptions to the concurrent bag.