The digitalization of public services is leading to a self-service model where users, including digitally skilled immigrants, are expected to access services independently. However, digitally skilled immigrants often face additional challenges compared to citizens due to administrative literacy gaps, cultural and language barriers, flawed e-government platforms and overcomplicated bureaucratic procedures. Generative AI conversational agents, like ChatGPT, have gained popularity for their ability to provide fast, personalized human-like answers. However, the use of Generative AI in the public sector raises concerns about accuracy, privacy, and the amplification of biases. Our research investigates how digitally skilled immigrants perceive GenAI conversational agents for bridging the lack of administrative literacy. We conducted a mixed-method study involving a survey and follow-up interviews with digitally skilled immigrants in four Nordic countries (Norway, Sweden, Denmark, and Finland). Our findings indicate that, on the one hand, GenAI tools have significant potential to bridge information gaps, particularly as browsing, translation, and explanation aids. On the other hand, using commercial tools in this context concerns many in terms of information accuracy and privacy. This study contributes to the literature on public service delivery and digital government automation, highlighting the benefits and challenges of implementing GenAI tools to support immigrants and addressing calls for research on the role of technology in facilitating the inclusion of immigrants in digital societies.