I am aware that there are other ways of implementing a priority queue e.g. using a sorted array/list.

ok, for the sake of the review I'll pretend I know only the List<>.

Queue or Stack?

• This should be a PriorityQueue so I suggest renaming TKey to TPriority and the Key property to Priority as this is what the key is, right?
• If you look a the .NET Queue<> it has methods like Enqueue, Dequeue or Peek which most users are familiar with and I find you shouldn't invent new names like Insert and DeleteX for these operations.
• Min and Max would better be First and Last as far as queues are concerned.

• But what is a queue?

  a queue represents a first-in, first-out collection of objects.

  so why does your queue have such methods as DeleteMax or DeleteLast and Max or PeekMax. You've mixed a stack with a queue here - this is confusing. It should either be queue or a stack. Not both.

  Try to mimic the original API when possible.

Default values

minKey = default(TKey);
maxKey = default(TKey);
minIndex = maxIndex = 0;

This is not necessary as their values are already default(TKey) and 0.

Good things

if (IsEmpty) throw new InvalidOperationException("Queue is empty");

This is rarely seen and just as it should be.

public PriorityQueue(int capacity)
{
    ..
}

public PriorityQueue() : this(10)
{
}

You use constructor overloading and chaining instead of default values. This is good too. If the 10 was only a constant it would be perfect.

A sorted list/array would work a lot faster, but since you are not interested I will comment on your implementation.

• Proper collections should implement at least IEnumerable and if suitable add indexer so you can provide a way of iterating that collection.

• Collections implementing IEnumerable have the option to provide collection initializer which internally used the Add() method, It must be called Add, Insert wont work, so you should rename your method to that and also add additional overload to that which accepts only TKey and TValue not QueueEntry<TKey, TValue> so you can make the intialization shorter.

  Examples:

  PriorityQueue<int, string> withQueueEntries = new PriorityQueue<int, string>
  {
      new QueueEntry<int, string>(1, "a"),
      new QueueEntry<int, string>(1, "b"),
      new QueueEntry<int, string>(1, "c"),
  };
  
  PriorityQueue<int, string> withEntries = new PriorityQueue<int, string>
  {
      {1, "a"},
      {1, "b"},
      {1, "c"},
  };
  

• Do not omit curly braces.

• If you know the index of the item to be removed you better use items.RemoveAt(index) instead of items.Remove(items[index]) the first one is faster the second one is always O(n) operation.

• I'm not a fan of multiple overloads when you can do it in a single one with optional parameters, but this is up to personal preference I guess.

With all of that your class can look like this:

public sealed class PriorityQueue<TKey, TValue> : IEnumerable<QueueEntry<TKey, TValue>>
    where TKey : IComparable<TKey>
{
    public int Count => items.Count;
    public bool IsEmpty => items.Count == 0;

    private readonly List<QueueEntry<TKey, TValue>> items;
    private TKey minKey;
    private TKey maxKey;
    private int minIndex;
    private int maxIndex;

    public PriorityQueue(int capacity)
    {
        items = new List<QueueEntry<TKey, TValue>>(capacity);
        minKey = default(TKey);
        maxKey = default(TKey);
        minIndex = maxIndex = 0;
    }

    public PriorityQueue() : this(10)
    {
    }

    public void Add(QueueEntry<TKey, TValue> entry)
    {
        if (entry == null)
        {
            throw new ArgumentNullException(nameof(entry));
        }

        var key = entry.Key;
        if (items.Count == 0) // first item
        {
            minKey = key;
            maxKey = key;
        }
        else if (key.CompareTo(minKey) < 0) // a new min key
        {
            minKey = key;
            minIndex = items.Count; // after the insert there will be one more entry.
        }
        else if (key.CompareTo(maxKey) > 0) // a new max key
        {
            maxKey = key;
            maxIndex = items.Count;
        }
        items.Add(entry);
    }

    public void Add(TKey entryKey, TValue entryValue)
    {
        if (entryKey == null)
        {
            throw new ArgumentNullException(nameof(entryKey));
        }
        if (entryValue == null)
        {
            throw new ArgumentNullException(nameof(entryValue));
        }
        Add(new QueueEntry<TKey, TValue>(entryKey, entryValue));
    }

    //Delete the entry with the min key; O(n).
    public void DeleteMin()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException("Queue is empty");
        }
        items.RemoveAt(minIndex);
        if (!IsEmpty)
        {
            minIndex = 0;
            for (var i = 1; i < items.Count; i++)
            {
                if (items[i].Key.CompareTo(items[minIndex].Key) < 0)
                {
                    minIndex = i;
                }
            }
            minKey = items[minIndex].Key;
        }
    }

    //Delete the entry with the max key; O(n).
    public void DeleteMax()
    {
        if (IsEmpty)
        {
            throw new InvalidOperationException("Queue is empty");
        }
        items.RemoveAt(maxIndex);
        if (!IsEmpty)
        {
            maxIndex = 0;
            for (var i = 0; i < items.Count; i++)
            {
                if (items[i].Key.CompareTo(items[maxIndex].Key) > 1)
                {
                    maxIndex = i;
                }
            }
            maxKey = items[maxIndex].Key;
        }
    }

    //O(1) to get min and max of the queue!
    public QueueEntry<TKey, TValue> Min => IsEmpty ? null : items[minIndex];

    public QueueEntry<TKey, TValue> Max => IsEmpty ? null : items[maxIndex];

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public IEnumerator<QueueEntry<TKey, TValue>> GetEnumerator()
    {
        return items.GetEnumerator();
    }
}

I haven't touched your QueueEntry class as it's something I would write and be happy about it.