Using latest Entity Framework 6.1.3 with Visual Studio 2015 and connecting to SQL Server 2016 developer edition, I had the following error:-
Could not determine storage version; a valid storage connection or a version hint is required.

Fix:-
In Visual Studio Solution Explorer.
Right Click over the Entity Framework .edmx
Open with and select XML Text Editor
Search for "ProviderManifestToken=" and either you will have XXXX or in my case I had 2012 in this value. So I changed it to 2008 and now my code works.