I have a custom solution (WSP) for SharePoint 2010, but we are now upgrading to SharePoint 2013.
If I upgrade my WSP project in Visual Studio 2012 to the latest version (so all references are .Net 4.0 assembly and other changes) and generate a new WSP, will I be able to deploy this newly generated WSP in SharePoint 2010 mode (in SharePoint 2013, with compatibility option)?
It depends on what resources does Your wsp contain. If there are images or pages, url paths are different in 2013, so links will be broken(by example /_layouts/ should become /_layouts/15, and so /images/).
And imho it is not necessary to change all references to .Net 4.0, but only sharepoint dlls, which have different version in 2013.
So
1) If You have no special resource in Your wsp, maybe it will work in 2013 without rebuild(it will be backward compatible)
2) Newly generated wsp will have different sharepoint dll versions, which 2010 does not contain.
There are some differences between 2013 and 2010 object models. Lately I migrated Sharepoint with a lot of custom code. Most of them moved smoothly even without any code rebuilding. But few of them mostly dependend on Search Service have had to be rewrited from scratch.
You can deploy your SharePoint 2010 in SharePoint 2013, there will be no issue in that, make sure that your SharePoint 2013 web application/site has all the list/libraries or content types and other resources which you have used in your WSP.
If you are thinking to deploy it as an provider hosted or auto-hosted app then you have to rebuild to custom solution.
