I am looking for an Archibald McAllister (various spellings including Mac Alester) who in the 1841 Census in St Quivox, Ayrshire, Scotland is recorded as being born around 1788 in Ireland. His marriage is recorded in St Quivox. I don't have anything more precise than that. What strategy would you suggest to try and track him down in Ireland. His name is not that unusual which combined with the patchiness of Irish records means I have no real idea where to start.
EDIT: I have added the census image below - Archibald is midway down the righthand column.