1. Only you can answer that. We would want an honest accounting of what happened. You should assume that programs will contact your old program to confirm your story, so it should match (they may not, but you should assume that they will).
2. Depends upon what your mistakes were. If you failed exams, then passing Step 3 would be helpful. If it was something else, then less so.
3. No right answer. I'd tend to lead off with it -- it will be clear from your application review, and you might as well just get it out of the way. Of note, your whole PS might be about how you've changed and why you're going to succeed this time.
4. Make sure you really know why you were let go. You say it wasn;t a professional issue, and your patient care was fine. Something doesn't add up.
Totally agree, the first and foremost question programs will need to answer for themselves is whether they can count on you to complete residency. For most programs there are plenty of applicants and they won't be taking risks on someone that's a liability to not finish (not saying this is you, but you absolutely need to address this in your application and be ready to discuss during interviews).
It certainly is possible that you were let go for a very low ITE. The ITE is an area of flux in many fields. Some fields (like IM) have stated that the ITE is supposed to be a private, internal metric of resident performance and not used for promotion / fellowships etc, other fields don't care and programs are free to use it any way they want. Now that we have these new milestones to deal with, we are all using the ITE to assess Medical Knowledge (and probably appropriately so). Although you might not get terminated for a low ITE, you might get terminated for a low MK assessment, which may be related. Complicated stuff.
However, it's also possible that your evaluations worsened over time because you didn't keep up. I've seen this before -- someone starts internship and does OK, but as internship progresses they don't move to that next level of actually managing patients, rather than just being a "reporter" or "getting stuff done that other people have decided". IN your case, you might have started out behind everyone else, then caught up to where an intern should be early in the year but not ready to promote. Whether to extend training (vs termination) depends on many factors, but often mainly on how much progress you are making (and how quickly).
The most important part of your application is going to be an LOR from your prior PD. They will describe in detail what happened in your prior program. My personal policy is that I share this letter with my residents -- I think it's important that they know what is in it, and I don't have anything to hide from them. Your PS can then focus on you -- how have you changed, why will this time be different, etc. You should not include evaluations in your application. Your PD letter will clarify that it wasn't a professionalism problem.
If you're not including a PD letter, then you probably should spell things out in your PS.