Nominating a professor for a fellowship
First make sure that you have read all the regulations for the award (in the case of ACM fellows: http://awards.acm.org/fellow_nom_guide.cfm). You see that the nomination in this case is quite some work. Especially question 3 is already answered there: You need five endorsers. Hence, it is expected that you "convince five people to support the nomination".

For question 2 it seems pretty clear that the ACM fellowship is really very competitive, so not getting the fellowship will not really hurt (not getting the Nobel price is also not a big deal for most people). 

For question 1: In my opinion you do not need to ask for permission. The awardees do not have any obligations so they will not have any burden from this award. I also think (but I am not sure about this) that is usual to not inform people that you want to nominate them. However, you need to provide a lot of information to the award giving institution and it is also not unusual to ask the person that you want to nominate "I (better: We) plan to nominate you for this award and would appreciate if you could provide us this and that information to prepare the nomination."