Can a 2NF relation be M:M?
The normal forms don't really have anything to do with many-to-many relationships.  If you happen to lose some as a byproduct of the normalization process, that's fine, but you won't generally do so.  If we consider that we have two tables: Salesman and Product which each have ID fields as their primary key and we have a third table called Specializes which shows which Salesmen specialize in selling which products.  This Specializes table would represent the many-to-many relationship since each salesman can specialize in multiple products and each product can be specialized in by more than one salesmen.  It would probably look something like this (excuse the awkward formatting, we can't do real tables on StackExchange):

| SalesmanID | ProductID |
|------------|-----------|
|  1         |  1        |
|  1         |  2        |
|  2         |  1        |
|  2         |  2        |
|  2         |  3        |
|------------|-----------|


Obviously, the lack of nulls and repeated rows means that this table is in 1NF.  In this table, the only candidate key is {SalesmanID, ProductID} and as such, there are no non-prime attributes.  It also contains no non-trivial functional dependencies.  Thus, it is necessarily in 2NF, 3NF, and BCNF.  I'm also going to assert without proof that it's in 4NF, 5NF, 6NF, and DKNF (to avoid having to explain all of the details thereof).  So really, no normal form removes many-to-many relationships, nor are they meant to.  The purpose of normal forms is not to remove many-to-many relationships (and I am not actually clear on why you would want to) but rather to remove potential insert anomalies, update anomalies, and deletion anomalies.  The primary role of the normal forms is to ensure that each piece of information is represented in a database table precisely once.  Having the same information embedded in multiple places leads to problems.  But that has nothing to do with many-to-many relationships.

I think that you mean to be asking a slightly different question about something like situations where a many-to-many relationship is embedded in a table which also tries to contain other information, such as if the table above contained the product name in addition to the product number (where name is functionally determined by number).  A table like that would either violate 2NF (if the name did not also functionally determine the number) or Boyce Codd Normal Form (if the name did functionally determine the number).

You could also perhaps be thinking of a different situation: when we have two unrelated 1:M relationships in the same table, such as if we were to add a third column to identify which language or languages each salesman speaks.

| SalesmanID | ProductID | Language |
|------------|-----------|----------|
|  1         |  1        | English  |
|  1         |  2        | English  |
|  2         |  1        | Spanish  |
|  2         |  2        | Spanish  |
|  2         |  3        | Spanish  |
|  2         |  1        | French   |
|  2         |  2        | French   |
|  2         |  3        | French   |
|------------|-----------|----------|


As you can see, that table is quite problematic, since we need 6 entries to express that Salesman 2 specializes in 3 products and speaks 2 languages.  This is a fourth normal form violation.

Edit:

Upon clarification, it's clear that what he's asking about is a table like the Specializes table, but with extra information about the salesmen and the products, essentially, a table which contains two entity sets and their many-to-many relationship in a single table.  So to answer that question directly, yes, you can have lousy tables like that which are in 3NF.  The normal form which guarantees that that won't happen is Boyce-Codd Normal Form (BCNF).  Here's an example of a lousy table like that which is vulnerable to all kinds of anomalies (insert, update, and delete), but is in 2NF and 3NF.

| SalesmanName | SalesmanID | ProductID | ProductName |
|--------------|------------|-----------|-------------|
|   Alex       |  1         |  1        |  Thingy     |
|   Alex       |  1         |  2        |  Whatsit    |
|   Barb       |  2         |  1        |  Thingy     |
|   Barb       |  2         |  2        |  Whatsit    |
|   Barb       |  2         |  3        |  Whoosit    |
|--------------|------------|-----------|-------------|


So, looking at this table, it's obviously in 1NF.  Further, we can identify the non-trivial functional dependencies very straightforwardly.  SalesmanName -> SalesmanID.  SalesmanID -> SalesmanName.  ProductID -> ProductName.  ProductName -> ProductID.  Next we need to identify the candidate keys.  There are four: {SalesmanName,ProductID}, {SalesmanName,ProductName}, {SalesmanID, ProductID}, and {SalesmanID, ProductName}.  As such, we have no non-prime attributes.  Thus, we are necessarily in 2NF (no functional dependencies between non-prime attributes) and 3NF (no non-trivial functional dependencies where the left-hand-side is not a super key and the right hand side contains a non-prime attribute).  However, we are not in BCNF because there do exist non-trivial functional dependencies whose left-hand-side is not a superkey.

Any similar situation will also always not be in Boyce-Codd Normal form because there will be some non-trivial functional dependency whose left-hand-side is not a superkey.  Any table like this will essentially have two entity sets each of whom have some attributes.  Basically, it will have a left entity set and a right entity set.  The left entity set will have some attributes which uniquely identify each left entity and the right entity set will have some attributes which uniquely identify each right entity.  Those will be involved in functional dependencies.  However, they will each not be candidate keys because you'll have to combine them to get a candidate key for the whole table.  As such, they won't be superkeys and there will be a Boyce-Codd Normal Form violation.  So BCNF will stop it cold.  Anything less than that will only catch some cases.  Really, if you only remember one normal form, it should be BCNF.