Would he even be allowed to take the test since he could not feel fear and thus, the ultimate reason for the test would not have any effect on Data?
The test would be valid for him. Even though he cannot feel fear, it would still determine how focused under pressure he would be. Even an unemotional android could freeze under pressure. The test was, after all, designed by a Vulcan, under the assumption that other Vulcans might take it.
That being said, I think Data would have done quite well, relatively speaking. He repeatedly demonstrated poise and composure under pressure in both command and non-command situations
Assuming passing involves responding appropriately, and not actually successfully completing the mission objectives, I think Data would have passed.
According to Memory Alpha in the Koyabashi Maru article, "The test is required for command-track cadets." That leaves the question of whether he's a command-track cadet. On the Enterprise, Data is third in command. He also has a constant desire to better himself and do as much as he can. In Redemption, Part II, Picard has had to re-assign many officers and put some in command positions. Data specifically asks why he was overlooked, indicating that Data does want to be able to command a starship (and Picard agrees he should, and assigns him to command the Sutherland). This shows that Data carries a desire to not just better himself, but to command a ship, so, given the option, would opt for the command-track.
And all command-track cadets take the Koyabashi Maru, so he would have taken it. Also, it's not just about fear. It's about stress and making the best decision possible when none will achieve your goal.
As to whether it would or would not have an effect on Data, that is just as important for any other office. In Peak Performance Data loses a game of strategema to a master player and assumes his programming is faulty. He removes himself from duty and, in effect, goes through a self-pity session until Picard orders him to get back into everything.
Data is not perfect and there are issues that arise in his programming. When faced with a no-win situation, Starfleet would have no idea what might happen to him. He might go into an infinite loop, he could shut down or do other things that aren't as easily to predict. From Starfleet's point of view, it would be as important to test Data in that scenario as it would be to test any other cadet.
What if, when the Klingons appeared, Data just stared at the viewscreen and started babbling about the uselessness of the scenario or something similar? As we saw, this very kind of thing happened after Data had been on active duty for years, including two years on the Enterprise, so a test to see how he'd behave under stress and unusual circumstances would be necessary.
He wouldn't, since the impossibility of the situation was logistical and not skill-dependent. A single ship had to enter the Neutral Zone, fight three heavily armed Klingon Warbirds, make sure they don't blow up a civilian ship that is dead in the water and return in one piece with the crew of the civilian ship.
The simulation is worse than the real thing: innovative solutions would be limited by the resources programmed into the simulation. For example, Data's solution to the once impossible-to-beat Picard Maneuver would not have worked in a simulation unless the actual behavior of interstellar matter had been programmed into the simulator.
So Data would fail the scenario.
Edit: Would he be allowed to take the test? I think Starfleet would insist that he take it. It is exactly the consequences of his lack of fear that his superior officers would want to observe. He would probably weigh the pros and cons and not attempt the rescue at all.
Edit #2: I'm wrong about that last statement. Here's what the Data we know would do: He would jettison the entire crew except himself on the Federation side of the border in pods and shuttles and then proceed to the rescue on his own. His abilities will allow him to control multiple systems without a crew. He would still probably get beaten, but only a ship and an android will be lost in the attempt. This is of course assuming that leaving the crew is allowed by the test's rules.
Canonically, we don't know for certain that Data took the test but we can assume that as Second Officer on the flagship of the Federation, he took it. Since the Kobayashi Maru is intended to be unwinnable, we can presume that he didn't succeed
Moving down the canon scale, Data and Picard administer the test (to Wesley) in the book TNG: Boogeymen. After Wesley fails it, Data offers him some commiseration; everyone fails, that's the point.
“Just coming off watch, Mr. Data?” Picard said.
Wesley suddenly knew what was coming. Why not? he thought. Why not invite the whole damn bridge crew?
“Yes, sir,” said Data.
“If you have nothing special planned, perhaps you would care to join Ensign Crusher and me on the holodeck. We’re going to run the Kobayashi Maru scenario.” Picard actually sounded as if he was looking forward to observing Wesley’s performance. But maybe he wasn’t just interested in Wesley. Maybe the captain was reliving his time at the Academy.
Picard shook his head. “You did nothing wrong. No one has ever triumphed over the Kobayashi Maru scenario.”
Data said, “Though legend has it that about eighty years ago, certain cadets fought it to a standstill.”
“Legend,” Picard said scornfully. “Academy scuttlebutt. The Kobayashi Maru is a no-win scenario—a test of character. Mr. Crusher did admirably. He did the only thing a moral captain could do. The fact that he was overwhelmed is unimportant.”
This isn't a difficult question
Data is logical and emotionless, he would simply play the scenario with the best chance of success (even if it was hopeless), he would simply try and fail like everyone else. The test has to have some weakness or everyone would just retreat. I.E if you were in a shuttle surrounded by 8 borg cubes - you would just run. So its reasonable to assume that Data would just fight the most likely way to achieve the objective
Plus if some people have fought it to a draw, it must have ways that 'have a small hope' of winning - Data would simple 'play the odds'
Its also possible he already passed the test (as in failed) as he is a commander too
The Kobayashi Maru test is one to test that the candidate doesn't freeze up, not do immoral things, and will try to carry out orders the best they can. You don't pass or fail based on whether you accomplish the mission. You pass or fail based on what you do to try to accomplish the mission. This is why Kirk passed. He didn't do anything "immoral" or anything that would make him not fit to be a Captain. Making the situation winnable can be considered part of the extended test. That noone had been able to do it before or since indicates a lacking of some measure by Starfleet officers in most cases.
Data, if he knew what the trick was in the Kobayashi Maru and if he knew about Kirk, he most certainly could in all likelihood do the same thing, however, Data probably wouldn't do it (nor would Picard, but for different reasons) because, quite simply, the situation is reversed for him in a lot of ways. If he tried to "fix" the program as Kirk did that would have been looked at as not being able to consider the circumstances and thus not fit to be in command of anyone. Likewise, he'd likely have to do things more cautious and spend more time searching for survivors even when they're clearly dead. Which means probably failed to accomplish the missions far harder than other candidates to show that he was fit for command.
The Kirk/Data comparisons are really fairly interesting when you stop and think of them. Though it does make me wonder if Kirk could break Data with a Kirk Speech...