Fortunately, Keflavík Airport is close to some good winter birding sites, even if it isn't exactly the most picturesque corner of the country. The main birding sites are Sandgerði, Garður (where the lighthouse is) and the harbours at Keflavík and Njarðvík.
Iceland Gull and Glaucous Gull should normally be easy to find in most harbours or coastal areas although numbers fluctuate throughout the winter depending on where the fish are. The best area is normally Sandgerði (4 miles from the airport), especially the area north of the harbour or the pools and coast at Garður. Iceland Gull is usually much more common than Glaucous in this area in late winter - there could be thousands of birds or single figures, depends on the fish.
Common Eider is common along every stretch of coast - if you don't see Common Eider in March in that area it means that Iceland has been obliterated by a meteorite. March is a very good month for King Eider, I've most often seen them in the harbour in Njarðvík at that time of year. The trick is to look through the big flocks of Common Eider which congregate in the harbour.
Common Redpoll is common in Reykjavík but I've never really looked for them in that area - they will certainly occur in Keflavík but it's just a question of running into them. They like birch trees. Hoary Redpoll is not very likely at all I am afraid, neither is Bohemian Waxwing - they occur in good numbers some years and not at all in others.
Black Guillemot could occur anywhere along the coast, again the harbour at Njarðvík would be a good bet but they are quite scarce in winter.
Gyr Falcon occurs throughout this area but it's just a matter of being in the right place at the right time - anywhere where there are large congregations of gulls and ducks is a good place to look for Gyr Falcon - I've seen them many times in Garður, Sandgerði and Njarðvík in winter time but it's also an easy bird to miss on such a whistlestop visit.
We have a lot of data for Iceland on eBird and it's very useful for getting an idea of which birds are where
http://ebird.org/ebird/GuideMe?repo...ocations=countries&continue.x=35&continue.y=8
Just click on the word "Map" next to the species name and it will give you sightings.
Also check the Birding Iceland Facebook page (can be viewed even if you are not a FB user, link in my signature below, as I put in sightings there and if there are any King Eiders around for example, there will be news there.