Correlating company entities between different data sources
First of all I would clean up INC, LLC, BV etcetera from both the sources. After this there are a few options. Since Levenshtein is a metric you can use metric trees to search your space more efficiently (about O(n*log(m))). This will still be very slow so there are approximations available, for example the cosine similarity on bi-grams of the names. You can do this using matrix multiplication which is both very efficient and easily distributable. Instead of taking the highest similarity you could take the top-n and do further analysis on these, for example the real Levenshtein distance. The fact that you have additional information could be useful, you could add this to your similarity function in some way but this will be guess work. Most of these ideas I got from a PyData meetup that was recorded, a speaker from ING (a big bank) discusses the exact problem you have albeit on a bigger set with less additional information:

https://www.youtube.com/watch?v=4ohTsblxOJs