Would App store accept a program that bundles a Python interpreter?
Before the Mac App Store

To improve your user's experience, you may be able to avoid needing to be in the Mac App Store.


Code sign your existing application and macOS's hostility towards your app will vanish.
Improve your application's first run experience using LetsMove. This open source framework will automatically copy the application into the /Applications folder and eject the disk image.
Use the open source Sparkle framework to add automated software updating to your application.


Just code signing your application will dramatically improve the first run experience for your users.

App Store Requirements

If your application meets the requirements below, then it will likely be accepted into the Mac App Store:


conforms to the App Store Guidelines;
supports being sandboxed;
can be bundled within a self contained application.


Ask Apple's iTunes Connect Team

You can contact Apple's iTunes Connect and talk to them before committing to significant development work. They are best placed to know what is likely to be accepted or not.