Cannot insert NULL into column while value is not null

So im having this weird problem with trying to add an instance to the entities. Its a asp.net application using EF 6.0.

The exception:

SqlException: Cannot insert the value NULL into column 'OrderId', table 'BETA.MDF.dbo.Orders'; column does not allow nulls. INSERT fails. The statement has been terminated.

My code:

User user = (User)Session["CurrentUser"];
BetaEntities entities = new BetaEntities();

Beta.Order order = new Beta.Order();
order.OrderId = Guid.NewGuid().ToString();
order.OrderDate = DateTime.Now;
order.OrderedBy = user.UserId;
order.HandledBy = entities.Users.Where(x => x.Rank > 0).Select(i => i.UserId).FirstOrDefault();

entities.Orders.Add(order);

entities.SaveChanges();

My table:

Also this is my order class, i already tried [Databasegenerated]

public partial class Order
{
    [Key]
    [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public string OrderId { get; set; }
    public System.DateTime OrderDate { get; set; }
    public int OrderedBy { get; set; }
    public int HandledBy { get; set; }
}

Example entry:

Please tell me if you need more details.

EDIT:

I tried setting the database datatype of OrderID to UNIQUEIDENTIEFIER and updated the entity model so the database should generate the guid(and i removed itself but i still get the same exception.

This is my new class:

public partial class Order
{
    [DatabaseGenerated(DatabaseGeneratedOption.Identity)]
    public System.Guid OrderId { get; set; }
    public System.DateTime OrderDate { get; set; }
    public int OrderedBy { get; set; }
    public int HandledBy { get; set; }
}

EDIT:

If i make OrderID NULLABALE and remove the primary key i get the following exception:

System.Data.Entity.Infrastructure.DbUpdateConcurrencyException: 'Store update, insert, or delete statement affected an unexpected number of rows (0). Entities may have been modified or deleted since entities were loaded. See http://go.microsoft.com/fwlink/?LinkId=472540 for information on understanding and handling optimistic concurrency exceptions.'

But this can be resolved by adding a primary key :( so removing the PK and making it NULLABLE isnt working.

Also i need to assign to GUID myself for further purposes so letting the database assign the guid itself(with [DatabaseGenerated(DatabaseGeneratedOption.Identity)]) is also not an option.