Best way to measure the execution time of methods

One way to do this would be to use an assembly weaver like 'Fody' with an extension that does exactly what you are looking for. Please see this link for an example extension: https://github.com/Fody/MethodTimer

How Fody works is it injects code into your code-base at compile time, utilising attributes as you have suggested in your question. The provided extension does just as you have described using a stopwatch to log the execution time of your code.

An example of usage:

Once the library is installed, you can add the annotation [Time] to the methods you wish to measure:

[Time]
public void TestMethod()
{
    //code here
}

You can then create a custom interceptor (A static class that will be automatically picked up by the Fody extension) which you can use to add a metric track into application insights:

public static class MethodTimeLogger
{
    public static void Log(MethodBase methodBase, long milliseconds)
    {
        var sample = new MetricTelemetry();
        sample.Name = methodBase.Name;
        sample.Value = milliseconds;
        // Your telemetryClient here
        telemetryClient.TrackMetric(sample);
    }
}

What I did was create an IDisposable class that would start a stopwatch in the constructor and stop/print the result in the dispose:

public class Superwatch : IDisposable
{
    static Stopwatch Watch = new Stopwatch();
    static Superwatch()
    {
        Watch.Start();
    }

    TimeSpan Start;
    public Superwatch()
    {
        Start = Watch.Elapsed;
    }

    public void Dispose()
    {
        TimeSpan elapsed = Watch.Elapsed - Start;
        Console.WriteLine($"Time elapsed: {elapsed}");
    }
} 

Then just pack the method into a using of an instance of the class you created.

using (var watch = new Superwatch())
{
      //piece of code
}

Not as clean as a decorator, but relatively clean imo and configurable for pieces of code.