You are trying to introduce the first Exchange 2013 server into an existing 2010 network, but running the 2013 setup complains that there are 2010 servers which doesn’t have SP3 applied in your environment.
But, you are sure that you have applied SP3 to all Exchange 2010 servers in your network. This issue will come up if you have 2010 Edge servers in place. Even though you have applied SP3 to the edge servers (which you should), the information in the Active Directory hasn’t been updated.
If you run Get-ExchangeServer in the Shell, you will see that the Edge servers will be shown as not having SP3 applied. The information in the AD is what the Edge servers “looked like” when the edge subscription was configured. Any subsequent changes to the Edge server is not written back to AD.
Hence, in order to fix this issue, you need to delete the existing edge subscription and create a new one. Once that is in place, run the Exchange 2013 setup and it should go through.
You can also update the info using ADSIEdit, but this is not supported ;)
To make it clear, all Exchange 2010 servers in your entire organization needs to be upgraded to SP3, whether they are in internet facing or not, same AD or different, including the Edge servers. All of them!