If a well-meaning person were to say he'd cross his fingers for you, what would be the correct response to be both halachically and socially correct? Would a non-response be sufficient (i.e. not saying thanks or acknowledging the statement in any other way)? How would you recommend responding politely and halachically in this situation?
Most likely you've been told (time and again) to not do X because it's somehow connected to Avodah Zarah. Those rules are for you, not for them.
Just say thanks and move on. The typical American saying "cross their fingers and toes" is not intending directly to worship idols. (Does this colleague regularly attend a non-monotheistic house of worship?)
A city mayor wanted to make a statue of the recently-assassinated President Kennedy, and asked the local rabbi to be on the planning board. Rabbi Moshe Feinstein noted (Igros YD2:54) that non-idolatrous statues are still prohibited for Jews, but allowed for non-Jews. He then pointed out that if the non-Jew first got it in his head to do something allowed for him, but not for us, we are allowed to encourage it. (The example is seeing your non-Jewish neighbor plowing on Shabbos; you can say "happy plowing!") He thus allowed it.
The crux here: there are all all sorts of things that we avoid because they have idolatrous origins or distant connections to idolatry, but they are not prohibited to the non-Jews as idolatry per se, in which case it's really not your problem what they do. "Cross my fingers and toes for you" seems like a good example of that.
In your case, if the non-Jewish colleague says "I'll pray for you", well ... they haven't said to whom ... it would have to be something where they say they will pray to a non-God ... even then, I'd go with "oh that's really not necessary, but thank you for the kind wishes." At which point what they choose to do is their business, not yours.