Do you have to do a 1391 analysis if the case is already in fed court via 1441?
The thing to note is that any case removed via 1441 only has one destination: the federal court embracing the place where the state court action was filed. This is true even if that federal court wouldn't have been proper venue in the first place. As long as ANY federal court would have had subject matter jurisdiction, it can be removed.
From there, yes either party could file a 1404 venue transfer for convenience. But they don't have to change venues unless they want to because 1391 doesn't apply to removed cases via 1441. If they do want to do a 1404 transfer than yes the new venue would need to comply with 1391. This is not true anymore after the Jurisdiction and Venue Clarification Act of 2011. Under the JVCA, a case can be transferred via §1404 to any venue to which all parties consent, even if it would not have been proper originally according to §1391.
Note also, you wouldn't use 1406, that's where the case is in an improper venue, because removed cases only have one destination and that venue is always proper.