What can the instructor do to overcome the Authenticity Bias in students?
Share their own struggles. Period. The instructor can start dispelling the myth by sharing his/her own story (replete with self-doubt, struggle, and frustration most likely) about studying computer science.

In Harvard's CS50 course, the professor shares his experience of not starting as a CS major and of essentially taking CS50 himself pass/fail. That's in the first lecture and communicates an important message about his journey not being one of simply innate talent. In another MOOC I've referenced before (Programming Languages from UW), the professor points out that he didn't write a line of code before college. As a student in each course through edX and Coursera, respectively, these small windows into the journeys of the professors has boosted my own confidence that one does not to be fluent in assembly at age 10 (exaggeration) to be a skilled programmer/computer scientist.

I share with students my own long and winding road that led me to CS. I share with them what I continue to study in my free time. I display old, poorly-written code. I recall one instance from teaching last year when I was trying to communicate to students how important it is to read program specifications and language documentation extremely carefully. From a homework assignment for Programming Languages, Part A, I kept figuratively banging my head against the desk because I was sure my logic and code were right, but I wasn't passing the checker. The problem: I was misunderstanding how a library function was working. Once I re-read the documentation and realized my error, the fix was trivial. Moments like this happen to everyone at every level of ability. Everyone struggles with something at some point.

Students need to see that the person teaching them is fallible, and that his/her knowledge has been gained through a lot of "blood, sweat, and tears," not because he/she wrote C code at age 5 (exaggeration again!) and never had a problem learning anything thereafter.

I also find some of the stories from freeCodeCamp inspiring. Their forum and Medium blog are filled with examples of individuals making career changes, working hard for an extended period of time, and achieving some level of "success." 

The bottom line: find stories to share that show students there are more people feeling what they feel than they might first imagine. Prove to them that computer science rewards hard work, discipline, and focus. In my mind, that starts with the person in the front of the room sharing his/her journey.