I think the biggest hassle in the short run is neither packaging nor the store, but the QML framework and System Integration. It is not too hard to have different packaging configurations in your repo and deploy to different stores.
Pure Maps by @rinigus is a great example on how platform independent mobile linux apps can be done. The most interesting part is the platform abstraction in QML, in my opinion. The app assumes some QML files in a folder called platform, which is just an imaginary interface to Elements like a Button, a Dialog, Clipboard or file chooser (aka Content Hub in UT). Adding support to another platform means to create a new platform folder and implement the interface using the specific platform frameworks stuff. The packager then just links the desired platform folder to platform and builds the app.
Now you may wonder whether it is necessary for each and every app developer to implement each platform support over and over again. And of course it is not. That could be done in one place shared by all apps. Someone has already started that meta-framework-project as a spin-off from Pure Maps, which just needs to be explored and picked up by app developers.
Sure, this won't solve all problems like (push) notification and background services. But it should help a majority of all apps to become available on many platforms.