If we have a web startup originally targetting users from country A, but the majority of users end up to be from America, is it sufficient to have the company incorporated in country A?
Additionally if the startup is providing paid services and has to receive money from the customers, what will be the best way to setup a receiving gateway? Should the merchant account be setup in country A or in America?
It depends on what you mean by "sufficient." It's certainly legal. You might be liable for certain sales taxes in the United States or have to pay franchise fees with certain states, but those are more complicated tax questions that deserve a tax attorney's expertise.
As for payment gateways, PayPal is international-friendly, but the problem you might face is the added skepticism US banks and credit card companies place on transactions with overseas merchants. The advantage to having a US-based merchant account is avoiding those red flags, automatically-declined charges, and suspicions of fraud. A US-based incorporated entity is one option for setting up a US bank account (consider Delaware as a domicile state), and some banks with an international presence might be able to help (JP Morgan Chase, BMO Harris, Bank of America, et cetera).