I have made an app that targets Windows 8.1, and on my phone i am running Windows 10 Mobile Insider Preview. Now while debugging with the emulator and the device i had no problems with the app, but i believe since the app is not showing up on Windows Store (App is in the store, published earlier today) while browsing with my phone it could have something to do with my version of Windows on the phone.
As the title says, can i make a project in VS2013 that targets both Windows 10 Mobile and Windows Phone 8.1 (or even 8?), and does Windows 10 Mobile find Windows 8.1 Apps in store?
You don't need to do anything special. An app targeting 8.1 would show up in the new store, and anyone would be able to download it.
It's possible that your app just hasn't been published yet. The publishing process takes quite a while, from hours to a day or two. Check out your store dashboard to verify your app's progress.