Hi Suvro and welcome to the Local Search forum.
Adding a new business directly to Google Maps UK can be done here:
I'm assuming you may have done this already without success; it could be that some verification failed or has not happened yet (or it could be that the address is out of the UK and keywords alone are not enough to qualify you as local).
Additionally, the UK local listings on Google were/are licensed from Thomson Local (but Google add much to that core data so it may diverge a lot over time, still getting to grips with how much though), so make sure you are in their free listings. Thomson Local will want you to have a UK address and phone number (which will be called to verify the listing). Once your business shows up, you can then claim the listing.
Doing the above may not ensure your company shows up in Google Local, but it's always good to have your company listed in as many free (and trusted) sources as possible - so getting listed with Yell and BT is advisable. Unfortunately, free listings don't always show up quickly and these companies may not list you if they suspect you don't have a legitimate (in their eyes) UK footprint.
The other way to get into a good position for UK results (both web search and local) is to have plenty of good uk inbound links and your properly-formatted UK address visible on the site.