Yep GREs definitely matter. When I started applying a faculty member told me that you should be above the 60th percentile in both sections to get in, and probably above 75th or 80th to be more competitive. However, I know people with lower that have also gotten in, and people with great GREs who haven't gotten in. They evaluate the application as a whole, so being strong in other areas will help pull up a low GRE sometimes.
I would say not having connections doesn't matter that much, but if you have some they can absolutely help.
As long as a program is APA accredited you should be good to work in the U.S. when you graduate.
This all sounds great! Good GPA's, great research experiences, and having a M.A. all help. If you are applying to labs with research that is in the same field as the research you have already done, you should be near the top of the pack in terms of research experiences. If you are applying to labs in different fields, it is still good, but you will have to make a clear statement of how your interests tie together. I would focus on doing well on the GRE, getting good LORs, writing a great statement, and applying to labs with a great fit. If you do that you should have a good chance! Good luck!