If no web service exists for this purpose, the next best solution is to interact programmatically with the PMCID/PMID/NIHMSID Converter web page. Of course, the downside is that your code breaks when the web page HTML is altered.
Several languages (Perl, Python, Ruby) provide a library named Mechanize for this purpose.
Here is some example code using the Ruby Mechanize library.
require 'mechanize'
agent = Mechanize.new
page = agent.get("http://www.ncbi.nlm.nih.gov/pmc/pmctopmid/")
form = page.forms[1] # the second form on the page
# now fill in the form
form.radiobutton_with(:value => "from_pmid").check # from PMID
form["PAFAppLayout.AppController.Page.PMCToPmidC.MainPortlet.Ids"] = "21707345\n23482678" # the PMID(s)
form.checkbox_with(:name => "PAFAppLayout.AppController.Page.PMCToPmidC.MainPortlet.ToFile").check # send to CSV file
# submit
f = agent.submit(form, form.buttons[1]) # second button on the form
f.save "ids.txt"
Result: a file named ids.txt in the directory from where you ran the code.
PMID,PMCID,NIHMSID
21707345,-,NIHMSID331689
23482678,PMC3592971,NIHMSID392341