As a workaround, I’m using this extension function in several of my projects:

fun <K,V> Pair<K,V>.toEntry() = object: Map.Entry<K,V> {
    override val key: K = first
    override val value: V = second
User story:

I had a method for adding attribute-value pairs to a URL:
addAttrs(items: List<UrlAttrValue?>)
List because you’re technically allowed to have multiple parameters with the same name, and if you do, their order becomes important.  I made a UrlAttrValue interface and a default AttrValue data class.  I think this is textbook Kotlin/Java OOP.
But the Java/Kotlin client code usually starts with a Map of key-value pairs and doesn’t care about order.  I found myself forgetting and writing new implementations of AttrValue (despite the existing UrlAttrValue).  Eventually, I realized, it’s just a pair (Pair).  An immutable key-value pair.  If I were using this code primarily from Kotlin, I would make it take a Pair, but it’s used a little more from Java, so what to do?
The best solution I could come up with was addAttrs(items: Iterable<Map.Entry<String, TaintedS?>?>).  I can now pass myMap.entries in Kotlin, myMap.entrySet() in Java.  But what about when there are duplicates and order is important?
I have been using a Tuple2 implements Map.Entry in Java for a few years now:
.addAttrs(vec(tup("duplicateAttr", taint("value1")),
              tup("duplicateAttr", taint("value2"))));
It made me expect that in Kotlin, I could:
.addAttrs(listOf("duplicateAttr" to taint("value1"),
                 "duplicateAttr" to taint("value2")))
I mean, I can use Tuple2 in Kotlin and it works fine.  I just found that having Tuple2<A,B> (an immutable pair) implement Map.Entry<K,V> has been incredibly convenient and not led to any confusion.  I’ve even gone so far as to implement SortedMap to store and return Tuple2’s (well, to alter Rich Hickey’s implementation to do that).
There could be a corner case where someone uses Pair in a way that should never be treated as a Map.Entry, but I can’t think of it.  If such a case ever exists, they could make their own class for it.  Or maybe even use a NOT Type.
 TrombaMarina:
I found myself forgetting the name UrlAttrValue and writing implementations of (I’d forgot there was already an AttrValue implementation). Eventually, I realized, it’s just a pair (Pair). An immutable key-value pair.
It looks like a Credential
data class Credential(val username:String, val password:String)
Should Credential implements UrlAttrValue and Map.Entry<String, String>?
              
I know this is a a pretty old thread, but having Pair implement Map.Entry would be extremely useful. If you look at e.g. org.apache.commons.lang3.tuple.Pair<A,B>, it implements Map.Entry<A,B> as well.
At the moment, I’m forced to use Apache Pair in many locations in my kotlin code for this very reason. I’d much rather stick to Kotlin’s own classes.
              
While I have to admit that I already missed the Map.Entry interface on Pair, I think that a pair should no nothing about a map! The elegant solution to this problem would be “structural typing”, which was already planned for Kotlin some years ago. But there were not much news about it and I guess it might be hard to implement it on the JVM. On the other hand, Scala managed to implement it. But Scala also does (did) a lot of things that Kotlin refuses to do (sometimes for good reasons!) like implicit conversions.
              
This is a very old topic, but for me it doesn’t make any sense to implement Entry by the Pair. Pair is a generic util, it should know nothing about collections or any other places where we use pair-like data structures. It makes sense Map knows about the Pair, but not the opposite.
It is really a common pattern that a component uses some data structure as its native type, then it still supports other similar types especially when passing the data to it. Internally, it handles conversions to its native data type. Looking from this perspective it would make sense the native type for Map is Map.Entry, we can construct a map using a list of entries and whenever it returns a collection of its entries, it also uses Map.Entry. At the same time it could still consume pairs and optionally, it could provide alternative functions to fetch its items as pairs.
Having said that… I agree, the situation with Map is pretty messy. We can’t create it from a list of Map.Entry, most probably because it is an interface and there is no basic implementation of it. Instead, we have to use pairs. Then, as @herman said, it sometimes returns Map.Entry and sometimes Pair which is even worse.
I don’t know if this is partially caused by the Java stdlib API, but anyway, unfortunately it can’t be fixed fully right now without introducing backward incompatible changes. Some extensions could help like Pair.toEntry() or Entry.toPair(), but we can also implement them ourselves in our project.
Map.Entry can be mutable (if the “optional” operation setValue is implemented), so it can’t / shouldn’t inherit from Pair which is immutable.
I fundamentally don’t understand this.  Isn’t Inheritance in Object Oriented Programming used to add methods/behaviors, such as ‘setters’?  In general, adding mutability may be unwise, but it’s still additional behavior.  I mean, that’s the basis of OOP, no?
 Glen.Peterson:
I fundamentally don’t understand this. Isn’t Inheritance in Object Oriented Programming used to add methods/behaviors, such as ‘setters’? In general, adding mutability may be unwise, but it’s still additional behavior. I mean, that’s how OOP works, no?
I think that depends if by “immutable” we mean “truly immutable” or “read only”. There is nothing wrong in adding mutability to read only types. We still can read from them. But truly immutable type and mutable type are incompatible with each other. If something is mutable it can’t be at the same time immutable.
[A] truly immutable type and mutable type are incompatible with each other. If something is mutable it can’t be at the same time immutable.
You’re saying making a subtype mutable destroys the “is-a” contract with the parent type?
“Behavioral subtyping is the principle that subclasses should satisfy the expectations of clients accessing subclass objects through references of superclass type, not just as regards syntactic safety (such as the absence of “method-not-found” errors) but also as regards behavioral correctness.”

Behavioral subtyping - Wikipedia
I need to think about this for maybe a year.  
I love the idea of ensuring deep immutability in a language or type-system.  Correct me if I’m wrong, but Kotlin does not provide that (yet).  Also, we probably are only talking about “implements” relationships here among interfaces, not extending classes with “inheritance.”
Kotlin’s collection interfaces all have their modifiable versions extend their unmodifiable versions.  Including MutableMap.MutableEntry.  It may be impure from a mutability-contract perspective, but in practice, it’s a big improvement over Java’s legacy Collection interfaces and a small enough step to facilitate 100% Java interop (if you’re careful).  Letting Pair implement Map.Entry seems like a low-hanging fruit, completely in line with Kotlin’s previous excellent Collection Interface design decisions.
              
Yes, there is no support for true immutability in both Java and Kotlin. Immutability is only a part of the contract, it’s a property of the implementation, not of the API of the type itself.
Again, this is purely hypothetical discussion, but if e.g. Kotlin 1.8.0 would make Pair open and add MutablePair : Pair, that would be technically correct, but it might break the existing code. Pair doesn’t mention immutability anywhere in the docs, but its current implementation is clearly immutable and it is closed for extension. If anyone assumed Pair always returns the same value consistently, after making it open the above assumption would be no longer true and the code might break.
              
Good points!  Interesting conversation!
To be clear, this question is only asking for:

Pair : Map.Entry

or something else that would yield similar convenience (+1 creativity for the idea of Map.Entry : Pair).
I’m now curious what backward-incompatible changes Pair : Map.Entry would cause?