I can use TypeDescriptor.AddAttributes to add an attribute to a type in runtime. How do I do the same for a method and parameter? (maybe 2 separate questions...)
TypeDescriptor.AddAttributes only affects a very specific use-case; i.e. from within System.ComponentModel. For the rest of reflection, it knows nothing about the extra attribute. And indeed, System.ComponentModel doesn't really apply to methods or parameters.
So in short; you can't. You will need to store this information somewhere else (bespoke), or add it at compile-time.
As I see from analyzing the TypeDescriptor class in Reflector, the .AddAttributes method internally calls the .AddProvider method. The TypeDescriptionProvider instance passed to it is actually responsible for providing meta-data. You could try adding the [TypeDescriptionProviderAttribute] attribute to your class and implement your own provider by deriving from the TypeDescriptionProvider class. As the documentation says, by overriding TypeDescriptionProvider.CreateInstance, you could provide a substitute object whose type has all necessary attributes. I suspect that the attributes applied to methods inside the substitution type will also take effect. However, I haven't tried that myself, so feel free to experiment...