The question is really too broad for us to answer. Anyone who tries to sell you something for X amount per month without reviewing your site and understanding your competition, is probably just after your money and doesn't care about long term safe success. If you live in Los Angeles, California, that is going to be much more difficult to target than if you live in Farah, Afghanistan. You can probably get results spending just $50 USD per month, if the person knows what they are doing. They should be able to give you a precise plan of what they will do for you, and you can always come back to this thread and ask if that's a good deal. Of course, you can probably get better results if you spend $100, and maybe even better results if you spend $200. Etc.
Most small businesses who are paying for SEO services are spending between $300 and $700 USD per month I would imagine. But the guy who pays $300 might be getting better results than the guy who pays $700, and the guy who pays $700 might be getting better results than someone paying $2000. The SEO services industry is very wild and most service providers do not like to be transparent with their fees. Their fee is usually based on the maximum they think they can get from you.
In General, local SEO isn't that difficult to get some nice results from. There are lots of things that local SEO service providers can do that your competition is not doing and it will give you a big boost in exposure online not just in the search engine results, but could be things like local service directories and such.
