There's a Wal-Mart in Ellsworth that might fit the bill. Be aware BH is a popular place for cruise ships. Here's the website for the schedule:
http://www.barharbormaine.gov/DocumentCenter/View/922. Right now it appears the first ship doesn't arrive until 5/6, which coincidentally is the same day that the Bar Harbor Oceanside KOA arrives. Some of the facilities in the park will be open by then as well as Blackwoods campground, but I'm not sure if you'll fit in there. No guarantee there won't be crowds, either. School groups and bus tours frequent the park. Won't be as bad as peak season but won't be dead, either.